×

SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. (English) Zbl 1398.90112

Summary: This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T., Conflict analysis in mixed integer programming, Discret. Optimiz., 4, 4-20 (2007) · Zbl 1169.90414
[2] Achterberg, T., Constraint integer programming, Ph.D. diss., TU Berlin, 2007, urn:nbn:de:0297-zib-11129. · Zbl 1430.90427
[3] Achterberg, T., SCIP: Solving constraint integer programs, Math. Program. Comput., 1, 1-41 (2009) · Zbl 1171.90476
[4] Achterberg, T. and Berthold, T., Hybrid branching, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, W.J. van Hoeve and J.N. Hooker, eds., Lecture Notes in Computer Science, Vol. 5547, Springer, Berlin, 2009, pp. 309-311.
[5] Achterberg, T., Berthold, T., Koch, T., and Wolter, K., Constraint integer programming: A new approach to integrate CP and MIP, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, Lecture Notes in Computer Science, Vol. 5015, Springer, Berlin, 2008, pp. 6-20. · Zbl 1142.68504
[6] Adjiman, C. S.; Dallwig, S.; Floudas, C. A.; Neumaier, A., A global optimization method, αBB, for general twice-differentiable constrained NLPs - I. Theoretical advances, Comput. Chem. Eng., 22, 1137-1158 (1998)
[7] Adjiman, C. S.; Androulakis, I. P.; Floudas, C. A., Global optimization of mixed-integer nonlinear problems, J. Amer. Instit. Chem. Eng., 46, 1769-1797 (2000)
[8] Ahadi-Oskui, T.; Vigerske, S.; Nowak, I.; Tsatsaronis, G., Optimizing the design of complex energy conversion systems by Branch and Cut, Comput. Chem. Eng., 34, 1226-1236 (2010)
[9] Bao, X., Automatic convexity detection for global optimization, Master’s thesis, University of Illinois at Urbana-Champaign, 2007.
[10] Beale, E.M.L., Branch and bound methods for numerical optimization of non-convex functions, in COMPSTAT 80 Proceedings in Computational Statistics, Physica-Verlag, Vienna, 1980, pp. 11-20.
[11] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634 (2009) · Zbl 1179.90237
[12] Belotti, P., Cafieri, S., Lee, J., and Liberti, L., Feasibility-based bounds tightening via fixed points, in Combinatorial Optimization and Applications, W. Wu and O. Daescu, eds., Lecture Notes in Computer Science, Vol. 6508, Springer, Berlin, 2010, pp. 65-76. · Zbl 1311.90189
[13] Belotti, P.; Miller, A.; Namazifar, M., Linear inequalities for bounded products of variables, SIAG/OPT Views-and-News, 12, 1-8 (2011)
[14] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172
[15] Belotti, P.; Bonami, P.; Fischetti, M.; Lodi, A.; Monaci, M.; Nogales-Gómez, A.; Salvagnin, D., On handling indicator constraints in mixed integer programming, Comput. Optim. Appl., 65, 545-566 (2016) · Zbl 1357.90094
[16] Bénichou, M.; Gauthier, J. M.; Girodet, P.; Hentges, G.; Ribiére, R.; Vincent, O., Experiments in mixed-integer linear programming, Math. Program., 1, 76-94 (1971) · Zbl 0233.90016
[17] Berthold, T., Primal heuristics for mixed integer programs, Master’s thesis, Technische Universität Berlin, 2006, urn:nbn:de:0297-zib-10293.
[18] Berthold, T., Measuring the impact of primal heuristics, Oper. Res. Lett., 41, 611-614 (2013) · Zbl 1287.90037
[19] Berthold, T., Heuristic algorithms in global MINLP solvers, Ph.D. diss., TU Berlin, 2014.
[20] Berthold, T., RENS - the optimal rounding, Math. Program. Comput., 6, 33-54 (2014) · Zbl 1304.90147
[21] Berthold, T. and Gleixner, A.M., Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering, in Proceedings of the European Workshop on Mixed Integer Nonlinear Programming (EWMINLP), April, CIRM Marseille, France, 2010, pp. 103-112.
[22] Berthold, T.; Gleixner, A. M., Undercover: A primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144, 315-346 (2014) · Zbl 1291.90144
[23] Berthold, T., Heinz, S., and Pfetsch, M.E., Nonlinear pseudo-Boolean optimization: Relaxation or propagation?, in Theory and Applications of Satisfiability Testing - SAT 2009, Lecture Notes in Computer Science, Vol. 5584, Springer, Berlin, 2009, pp. 441-446.
[24] Berthold, T., Heinz, S., and Vigerske, S., Extending a CIP framework to solve MIQCPs, in Lee and Leyffer [59], pp. 427-444. · Zbl 1242.90120
[25] Berthold, T., Heinz, S., Lübbecke, M., Möhring, R.H., and Schulz, J., A constraint integer programming approach for resource-constrained project scheduling, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 6140, Springer, Berlin, 2010, pp. 313-317. · Zbl 1285.90045
[26] Berthold, T., Heinz, S., Pfetsch, M.E., and Vigerske, S., Large neighborhood search beyond MIP, in Proceedings of the 9th Metaheuristics International Conference (MIC 2011), urn:nbn:de:0297-zib-12989, 2011, pp. 51-60.
[27] Berthold, T.; Gleixner, A. M.; Heinz, S.; Vigerske, S., Analyzing the computational impact of MIQCP solver components, Numer. Algebra, Control Optim., 2, 739-748 (2012) · Zbl 1269.90066
[28] Bixby, R. E., Solving real-world linear programs: A decade and more of progress, Oper. Res., 50, 3-15 (2002) · Zbl 1163.90643
[29] Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., and Wunderling, R., MIP: Theory and practice – closing the gap, in System Modelling and Optimization: Methods, Theory and Applications, M.J.D. Powell and S. Scholtes, eds., Kluwer Dordrecht, 2000, pp. 19-49. · Zbl 0986.90025
[30] Burer, S.; Letchford, A. N., Non-convex mixed-integer nonlinear programming: A survey, Surv. Oper. Res. Manage. Sci., 17, 97-106 (2012)
[31] Bussieck, M.R. and Vigerske, S., MINLP solver software, in Wiley Encyclopedia of Operations Research and Management Science, J.J.C. et.al., ed., Wiley & Sons, Inc., 2010.
[32] Bussieck, M. R.; Drud, A. S.; Meeraus, A., MINLPLib - a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119 (2003) · Zbl 1238.90104
[33] Caprara, A.; Locatelli, M., Global optimization problems and domain reduction strategies, Math. Program., 125, 123-137 (2010) · Zbl 1198.90325
[34] Danna, E., Performance variability in mixed integer programming, Talk at Workshop on Mixed Integer Programming 2008, Columbia University, New York, NY, USA, 2014.
[35] Danna, E.; Rothberg, E.; Pape, C. L., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 71-90 (2004) · Zbl 1131.90036
[36] Domes, F.; Neumaier, A., Constraint propagation on quadratic constraints, Constraints, 15, 404-429 (2010) · Zbl 1208.68200
[37] Falk, J. E.; Hoffman, K. R., A successive underestimation method for concave minimization problems, Math. Oper. Res., 1, 251-259 (1976) · Zbl 0362.90082
[38] Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 23-47 (2003) · Zbl 1060.90056
[39] Floudas, C. A., Nonlinear and Mixed Integer Optimization: Fundamentals and Applications (1995), Oxford University Press: Oxford University Press, New York · Zbl 0886.90106
[40] Floudas, C. A.; Akrotirianakis, I. G.; Caratzoulas, S.; Meyer, C. A.; Kallrath, J., Global optimization in the 21st century: Advances and challenges, Comput. Chem. Eng., 29, 1185-1202 (2005)
[41] Forrest, J. J.H.; Tomlin, J. A., Branch and bound, integer, and non-integer programming, Ann. Oper. Res., 149, 81-87 (2007) · Zbl 1213.90018
[42] Fourer, R.; Maheshwari, C.; Neumaier, A.; Orban, D.; Schichl, H., Convexity and concavity detection in computational graphs: Tree walks for convexity assessment, INFORMS J. Comput., 22, 26-43 (2009) · Zbl 1243.90004
[43] Gamrath, G., Fischer, T., Gally, T., Gleixner, A.M., Hendel, G., Koch, T., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J.T., and Witzig, J., The SCIP Optimization Suite 3.2, ZIB Report 15-60, Zuse Institute, Berlin, 2016, urn:nbn:de:0297-zib-57675.
[44] Gau, C. and Schrage, L., Implementation and testing of a branch-and-bound based method for deterministic global optimization: Operations research applications, in Frontiers in Global Optimization, C.A. Floudas and P.M. Pardalos, eds., Nonconvex Optimization and Its Applications, Vol. 74, Springer, 2003, pp. 145-164. · Zbl 1165.90687
[45] Gay, D.M., Bounds from slopes, Tech. Rep., Sandia National Laboratories, 2010. Available at .
[46] Ghosh, S., DINS, a MIP improvement heuristic, in Integer Programming and Combinatorial Optimization - 12th International Conference, M. Fischetti and D.P. Williamson, eds., Lecture Notes in Computer Science, Vol. 4513, Springer, Berlin, 2007, pp. 310-323. · Zbl 1136.90419
[47] Gleixner, A.M. and Weltge, S., Learning and propagating lagrangian variable bounds for mixed-integer nonlinear programming, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013, C. Gomes and M. Sellmann, eds., LNCS, Vol. 7874, Springer, Berlin, 2013, pp. 355-361. · Zbl 1382.90063
[48] Gleixner, A. M.; Berthold, T.; Müller, B.; Weltge, S., Three enhancements for optimization-based bound tightening, J. Global Optim., 67, 731-757 (2017) · Zbl 1369.90106
[49] Gounaris, C. E.; Floudas, C. A., A review of recent advances in global optimization, J. Global Optim., 45, 3-38 (2009) · Zbl 1180.90245
[50] Grossmann, I.E. and Kravanja, Z., Mixed-integer nonlinear programming: A survey of algorithms and applications, in Large-Scale Optimization with Applications, Part II: Optimal Design and Control, A.R. Conn, L.T. Biegler, T.F. Coleman, and F.N. Santosa, eds., The IMA Volumes in Mathematics and its Applications, Vol. 93, Springer, New York, NY, 1997, pp. 73-100. · Zbl 0884.65058
[51] Grossmann, I. E.; Lee, J., Cyberinfrastructure for mixed-integer nonlinear programming, SIAG/OPT Views-and-News, 22, 8-12 (2011)
[52] Hendel, G., Empirical analysis of solving phases in mixed integer programming, Master’s thesis, Technische Universität Berlin, 2014, urn:nbn:de:0297-zib-54270.
[53] Hooker, J. N., Integrated Methods for Optimization, 170 (2007), Springer: Springer, New York · Zbl 1214.90084
[54] Horst, R.; Pardalos, P., Handbook of Global Optimization, 2 (1995), Kluwer Academic Publishers · Zbl 0805.00009
[55] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1990), Springer: Springer, Berlin · Zbl 0704.90057
[56] Khachiyan, L. G., A polynomial algorithm in linear programming, Doklady Akademii Nauk SSSR, 244, 1093-1096 (1979) · Zbl 0414.90086
[57] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R. E.; Danna, E.; Gamrath, G.; Gleixner, A. M.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, D. E.; Wolter, K., MIPLIB 2010 - mixed integer programming library version 5, Math. Program. Comput., 3, 103-163 (2011)
[58] Land, A. H.; Doig, A. G., An automatic method of solving discrete programming problems, Econometrica, 28, 497-520 (1960) · Zbl 0101.37004
[59] Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming, 154 (2012), Springer, New York · Zbl 1230.90005
[60] Liberti, L.; Pantelides, C. C., Convex envelopes of monomials of odd degree, J. Global Optim., 25, 157-168 (2003) · Zbl 1030.90117
[61] Locatelli, M.; Schoen, F., Global Optimization: Theory, Algorithms, and Applications, 15 (2013), SIAM · Zbl 1286.90003
[62] Maranas, C. D.; Floudas, C. A., Global optimization in generalized geometric programming, Comput. Chem. Eng., 21, 351-369 (1997) · Zbl 0891.90165
[63] Mccormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I - convex underestimating problems, Math. Program., 10, 147-175 (1976) · Zbl 0349.90100
[64] Millman, K. J.; Aivazis, M., Python for scientists and engineers, Comput. Sci. Eng., 13, 9-12 (2011)
[65] Misener, R.; Floudas, C. A., GloMIQO: Global mixed-integer quadratic optimizer, J. Global Optim., 57, 3-50 (2012) · Zbl 1272.90034
[66] Misener, R.; Floudas, C. A., ANTIGONE: Algorithms for continuous / integer global optimization of nonlinear equations, J. Global Optim., 59, 503-526 (2014) · Zbl 1301.90063
[67] Mönnigmann, M., Efficient calculation of bounds on spectra of Hessian matrices, SIAM J. Scient. Comput., 30, 2340-2357 (2008) · Zbl 1181.65055
[68] Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall, Englewood Cliffs, NJ · Zbl 0176.13301
[69] Moore, R. E.; Kearfott, R. B.; Cloud, M. J., Introduction to Interval Analysis (2009), SIAM · Zbl 1168.65002
[70] Nenov, I.P., Fylstra, D.H., and Kolev, L.V., Convexity determination in the Microsoft Excel solver using automatic differentiation techniques, Extended abstract, Frontline Systems Inc., 2004. Available at .
[71] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer, New York · Zbl 1104.65059
[72] Nowak, I., Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming, 152 (2005), Birkhäuser Verlag: Birkhäuser Verlag, Basel · Zbl 1089.90039
[73] Nowak, I.; Vigerske, S., LaGO: A (heuristic) branch and cut algorithm for nonconvex MINLPs, Cent. Eur. J. Oper. Rese., 16, 127-138 (2008) · Zbl 1152.90665
[74] Oliphant, T. E., Python for scientific computing, Comput. Sci. Eng., 9, 10-20 (2007)
[75] Pintér, J. D., Global Optimization: Scientific and Engineering Case Studies, 85 (2006), Springer · Zbl 1103.90011
[76] Pratt, J. W., Remarks on zeros and ties in the Wilcoxon signed rank procedures, J. Amer. Statist. Assoc., 54, 655-667 (1959) · Zbl 0086.35101
[77] Quesada, I.; Grossmann, I. E., Global optimization algorithm for heat exchanger networks, Indus. Eng. Chem. Res., 32, 487-499 (1993)
[78] Quesada, I.; Grossmann, I. E., A global optimization algorithm for linear fractional and bilinear programs, J. Global Optim., 6, 39-76 (1995) · Zbl 0835.90074
[79] Rothberg, E., An evolutionary algorithm for polishing mixed integer programming solutions, INFORMS J. Comput., 19, 534-541 (2007) · Zbl 1241.90092
[80] Ryoo, H. S.; Sahinidis, N. V., A branch-and-reduce approach to global optimization, J. Global Optim., 8, 107-138 (1996) · Zbl 0856.90103
[81] Savelsbergh, M. W.P., Preprocessing and probing techniques for mixed integer programming problems, INFORMS J. Comput., 6, 445-454 (1994) · Zbl 0814.90093
[82] Schichl, H.; Neumaier, A., Interval analysis on directed acyclic graphs for global optimization, J. Global Optim., 33, 541-562 (2005) · Zbl 1094.65061
[83] Smith, E. M.B.; Pantelides, C. C., A symbolic reformulation/spatial branch-and-bound algorithm for the global optimization of nonconvex MINLPs, Comput. Chem. Eng., 23, 457-478 (1999)
[84] Tawarmalani, M.; Sahinidis, N. V., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, 65 (2002), Kluwer Academic Publishers · Zbl 1031.90022
[85] Tawarmalani, M.; Sahinidis, N. V., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[86] Vavasis, S.A., Complexity issues in global optimization: A survey, in Horst and Pardalos [54], pp. 27-41. · Zbl 0836.90138
[87] Vigerske, S., Decomposition of multistage stochastic programs and a constraint integer programming approach to mixed-integer nonlinear programming, Ph.D. diss., Humboldt-Universität zu Berlin, 2013, urn:nbn:de:kobv: 11-100208240.
[88] Vu, X.-H.; Schichl, H.; Sam-Haroud, D., Interval propagation and search on directed acyclic graphs for numerical constraint solving, J. Global Optim., 45, 499-531 (2009) · Zbl 1179.90267
[89] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542
[90] Wilcoxon, F., Individual comparisons by ranking methods, Biomet. Bull, 1, 80-83 (1945)
[91] Zamora, J. M.; Grossmann, I. E., A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms, J. Global Optim., 14, 217-249 (1999) · Zbl 0949.90097
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.