×

zbMATH — the first resource for mathematics

Conflict analysis for MINLP. (English) Zbl 07362326
Summary: The generalization of mixed integer program (MIP) techniques to deal with nonlinear, potentially nonconvex, constraints has been a fruitful direction of research for computational mixed integer nonlinear programs (MINLPs) in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers toward the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared toward two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.
Summary of Contribution: This original article concerns the advancement of exact general-purpose algorithms for solving one of the largest and most prominent problem classes in optimization, mixed integer nonlinear programs (MINLPs). It demonstrates how methods for conflict analysis that learn from infeasible subproblems can be transferred to nonlinear optimization. Further, it develops theory for how nonlinear dual infeasibility proofs can be derived from a nonlinear relaxation. This paper features a thoroughly computational study regarding the impact of conflict analysis techniques on the overall performance of a state-of-the-art MINLP solver when solving MINLPs to global optimality.
MSC:
90Cxx Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T (2007a) Conflict analysis in mixed integer programming. Discrete Optim. 4(1):4-20.Crossref, Google Scholar · Zbl 1169.90414
[2] Achterberg T (2007b) Constraint integer programming. PhD thesis, Technische Universität Berlin, Germany.Google Scholar
[3] Achterberg T , Berthold T (2009) Hybrid branching. van Hoeve WJ , Hooker JN , eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems, Proc. 6th Internat. Conf. (CPAIOR). Lecture Notes in Computer Science 5547 (Springer, Berlin Heidelberg), 309-311.Google Scholar
[4] Achterberg T , Wunderling R (2013) Mixed integer programming: Analyzing 12 years of progress. Jünger M , Reinelt G , eds. Facets of Combinatorial Optimization (Springer, Berlin Heidelberg), 449-481.Crossref, Google Scholar · Zbl 1317.90206
[5] Belotti P , Berthold T , Neves K (2016) Algorithms for discrete nonlinear optimization in FICO Xpress. 2016 IEEE Sensor Array Multichannel Signal Processing Workshop (SAM), 1-5 (IEEE, Washington, DC).Google Scholar
[6] Belotti P , Lee J , Liberti L , Margot F , Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Software 24(4-5):597-634.Crossref, Google Scholar · Zbl 1179.90237
[7] Belotti P , Kirches C , Leyffer S , Linderoth J , Luedtke J , Mahajan A (2013) Mixed-integer nonlinear optimization. Acta Numerica 22:1-131, http://dx.doi.org/10.1017/S0962492913000032.Google Scholar · Zbl 1291.65172
[8] Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238-252.Crossref, Google Scholar · Zbl 0109.38302
[9] Berthold T (2013) Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6):611-614.Google Scholar · Zbl 1287.90037
[10] Berthold T , Feydy T , Stuckey PJ (2010) Rapid learning for binary programs. Lodi A , Milano M , Toth P , eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems, Proc. 7th Internat. Conf. (CPAIOR). Lecture Notes in Computer Science 6140 (Springer, Berlin Heidelberg), 51-55.Google Scholar · Zbl 1285.68151
[11] Berthold T , Stuckey PJ , Witzig J (2019) Local rapid learning for integer programs. Rousseau LM , Stergiou K , eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham), 67-83.Google Scholar · Zbl 07116686
[12] Biegler LT , Grossmann IE , Westerberg AW (1997) Systematic Methods for Chemical Process Design, (Pearson, Upper Saddle River, NJ).Google Scholar
[13] Bixby RE (2002) Solving real-world linear programs: A decade and more of progress. Oper. Res. 50(1):3-15.Link, Google Scholar · Zbl 1163.90643
[14] Bonami P , Biegler LT , Conn AR , Cornuéjols G , Grossmann IE , Laird CD , Lee J , et al. . (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5(2):186-204.Crossref, Google Scholar · Zbl 1151.90028
[15] Boyd SP , Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Google Scholar
[16] Chakravarti N (1994) Some results concerning post-infeasibility analysis. Eur. J. Oper. Res. 73(1):139-143.Google Scholar · Zbl 0806.90082
[17] Chinneck JW , Dravnieks EW (1991) Locating minimal infeasible constraint sets in linear programs. ORSA J. Comput. 3(2):157-168.Google Scholar · Zbl 0755.90055
[18] Coey C , Lubin M , Vielma JP (2020) Outer approximation with conic certificates for mixed-integer convex problems. Math. Programming Comput. 12(2):249-293.Google Scholar · Zbl 1441.90095
[19] Cornuéjols G , Tütüncü R (2006) Optimization Methods in Finance , vol. 5 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1117.91031
[20] Dakin RJ (1965) A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3):250-255.Crossref, Google Scholar · Zbl 0154.42004
[21] Davey B , Boland N , Stuckey PJ (2002) Efficient intelligent backtracking using linear programming. INFORMS J. Comput. 14(4):373-386.Link, Google Scholar · Zbl 1238.90144
[22] Dolan ED , Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201-213.Crossref, Google Scholar · Zbl 1049.90004
[23] Duran MA , Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36(3):307-339.Crossref, Google Scholar · Zbl 0619.90052
[24] Fletcher R , Leyffer S (1994) Solving mixed integer nonlinear programs by outer approximation. Math. Programming 66(1-3):327-349.Crossref, Google Scholar · Zbl 0833.90088
[25] Fletcher R , Leyffer S (1998) User manual for filtersqp. Numerical Analysis Report NA/181, Department of Mathematics, University of Dundee, Scotland.Google Scholar
[26] Floudas CA (2000) Global optimization in design and control of chemical process systems. J. Process Control 10(2):125-134.Google Scholar
[27] Forsgren A , Gill PE , Wong E (2016) Primal and dual active-set methods for convex quadratic programming. Math. Programming 159(1-2):469-508.Crossref, Google Scholar · Zbl 1346.90652
[28] Ginsberg ML (1993) Dynamic backtracking. J. Artificial Intelligence Res. 1:25-46.Crossref, Google Scholar · Zbl 0900.68179
[29] Gleeson J , Ryan J (1990) Identifying minimally infeasible subsystems of inequalities. ORSA J. Comput. 2(1):61-63.Google Scholar · Zbl 0752.90050
[30] Gleixner A , Bastubbe M , Eifler L , Gally T , Gamrath G , Gottwald RL , Hendel G , et al. . (2018) The SCIP Optimization Suite 6.0. ZIB-Report 18-26, Zuse Institute Berlin, Germany, http://nbn-resolving.de/urn:nbn:de:0297-zib-69361.Google Scholar
[31] Gould N , Scott J (2016) A note on performance profiles for benchmarking software. ACM Trans. Math. Software 43(2):1-5.Crossref, Google Scholar · Zbl 1369.65202
[32] Gupta OK , Ravindran A (1985) Branch and bound experiments in convex nonlinear integer programming. Management Sci. 31(12):1533-1546.Link, Google Scholar · Zbl 0591.90065
[33] Horst R , Tuy H (2013) Global Optimization: Deterministic Approaches (Springer Science & Business Media, Springer-Verlag, Heidelberg, Berlin).Google Scholar
[34] Jiang Y , Richards T , Richards B (1994) No-good backmarking with min-conflict repair in constraint satisfaction and optimization. Borning A , ed. Principles Practice Constraint Programming, Proc. 2nd Annual Workshop (PPCP). Lecture Notes in Computer Science 874 (Springer, Berlin, Heidelberg), 21-39.Google Scholar
[35] Kallrath J (2005) Solving planning and design problems in the process industry using mixed integer and global optimization. Annals Oper. Res. 140(1):339-373.Google Scholar · Zbl 1091.90089
[36] Kellner K , Pfetsch ME , Theobald T (2019) Irreducible infeasible subsystems of semidefinite systems. J. Optim. Theory Appl. 181(3):727-742.Google Scholar · Zbl 1414.90258
[37] Khachiyan LG (1979) A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR . 244:1093-1096.Google Scholar · Zbl 0414.90086
[38] Kılınç MR , Sahinidis NV (2018) Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. Optim. Methods Software 33(3):540-562.Crossref, Google Scholar · Zbl 1398.90110
[39] Kılınç Karzan F , Nemhauser GL , Savelsbergh MWP (2009) Information-based branching schemes for binary linear mixed-integer programs. Math. Programming Comput. 1(4):249-293.Crossref, Google Scholar · Zbl 1184.90114
[40] Kocis GR , Grossmann IE (1988) Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis. Indust. Engrg. Chemical Res. 27(8):1407-1421.Crossref, Google Scholar
[41] Kronqvist J , Lundell A , Westerlund T (2016) The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. J. Global Optim. 64(2):249-272.Crossref, Google Scholar · Zbl 1339.90247
[42] Kronqvist J , Bernal D , Lundell A , Grossmann I (2018) A review and comparison of solvers for convex MINLP. https://link.springer.com/article/10.1007/s11081-018-9411-8.Google Scholar
[43] Kuhn HW , Tucker AW (1951) Nonlinear programming. Neyman J , ed. Proc. 2nd Berkeley Symp. Math. Statist. Probab. (University of California Press, Berkeley), 481-492.Google Scholar
[44] Land AH , Doig AG (1960) An automatic method of solving discrete programming problems. Econometrica 28(3):497-520.Google Scholar · Zbl 0101.37004
[45] Lemke CE (1954) The dual method of solving the linear programming problem. Naval Res. Logist. Quart. 1(1):36-47.Google Scholar
[46] Liberti L , Pantelides CC (2003) Convex envelopes of monomials of odd degree. J. Global Optim. 25(2):157-168.Google Scholar · Zbl 1030.90117
[47] Liberti L , Lavor C , Maculan N (2008) A branch-and-prune algorithm for the molecular distance geometry problem. Internat. Trans. Oper. Res. 15(1):1-17.Google Scholar · Zbl 1136.92037
[48] Liberti L , Lavor C , Maculan N , Nascimento MAC (2009) Reformulation in mathematical programming: An application to quantum chemistry. Discrete Appl. Math. 157(6):1309-1318.Google Scholar · Zbl 1173.90494
[49] Lodi A , Tramontani A (2013) Performance variability in mixed-integer programming. Theory Driven by Influential Applications (INFORMS, Catonsville, MD), 1-12.Google Scholar
[50] Lundell A , Kronqvist J (2019) On solving nonconvex MINLP problems with SHOT. Advances in Intelligent Systems and Computing (Springer International Publishing, Cham), 448-457.Google Scholar
[51] Mahajan A , Leyffer S , Linderoth J , Luedtke J , Munson T (2017) Minotaur: A mixed-integer nonlinear optimization toolkit. Preprint, submitted March 22, 2020, https://link.springer.com/article/10.1007/s12532-020-00196-1.Google Scholar
[52] Marques-Silva JP , Sakallah K (1999) Grasp: A search algorithm for propositional satisfiability. IEEE Trans. Comput. 48(5):506-521.Google Scholar · Zbl 1392.68388
[53] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147-175.Google Scholar · Zbl 0349.90100
[54] McGill R , Tukey JW , Larsen WA (1978) Variations of box plots. Amer. Statistician 32(1):12-16.Google Scholar
[55] Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4):575-601.Google Scholar · Zbl 0773.90047
[56] Mészáros C (1999) The BPMPD interior point solver for convex quadratic problems. Optim. Methods Software 11(1-4):431-449.Google Scholar · Zbl 0973.90521
[57] Misener R , Floudas CA (2014) ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J. Global Optim. 59(2-3):503-526.Google Scholar · Zbl 1301.90063
[58] Murty KG , Yu FT (1988) Linear Complementarity, Linear and Nonlinear Programming , vol. 3 (Heldermann, Berlin).Google Scholar
[59] Nocedal J , Wright SJ (2006) Nonlinear Equations (Springer, New York).Google Scholar
[60] Phillips AT , Rosen JB (1994) A quadratic assignment formulation of the molecular conformation problem. J. Global Optim. 4(2):229-241.Google Scholar · Zbl 0797.90116
[61] Quesada I , Grossmann IE (1992) An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chemical Engrg. 16(10-11):937-947.Google Scholar
[62] Sandholm T , Shields R (2006) Nogood learning for mixed integer programming. Workshop on Hybrid Methods and Branching Rules in Combinatorial Optimization. CMU Computer Science Department Technical report CMU-CS-06-155, Concordia University, Montréal, Canada.Google Scholar
[63] Stallman RM , Sussman GJ (1977) Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence 9(2):135-196.Google Scholar · Zbl 0372.94024
[64] Tawarmalani M , Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225-249.Crossref, Google Scholar · Zbl 1099.90047
[65] Vavasis SA (1995) Complexity issues in global optimization: A survey. Horst R, Pardalos PM, eds. Handbook of Global Optimization (Springer, Boston), 27-41. Crossref, Google Scholar · Zbl 0836.90138
[66] Vigerske S , Gleixner A (2018) SCIP: Global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Software 33(3):563-593.Google Scholar · Zbl 1398.90112
[67] Viswanathan J , Grossmann I (1990) A combined penalty function and outer-approximation method for minlp optimization. Comput. Chemical Engrg. 14(7):769-782.Google Scholar
[68] Wächter A , Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25-57.Google Scholar · Zbl 1134.90542
[69] Westerlund T , Pettersson F (1995) An extended cutting plane method for solving convex minlp problems. Comput. Chemical Engrg. 19:131-136.Google Scholar
[70] Witzig J , Gleixner A (2020) Conflict-driven heuristics for mixed integer programming. INFORMS J. Comput. , ePub ahead of print October 8, https://doi.org/10.1287/ijoc.2020.0973.Link, Google Scholar
[71] Witzig J , Berthold T , Heinz S (2017) Experiments with conflict analysis in mixed integer programming. Salvagnin D, Lombardi M, eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems, Proc. 14th Internat. Conf. (CPAIOR). Lecture Notes in Computer Science 10335 (Springer, Berlin, Heidelberg), 211-220.Google Scholar · Zbl 06756587
[72] Witzig J , Berthold T , Heinz S (2019a) Computational aspects of infeasibility analysis in mixed integer programming. Technical Report 19-54, Zuse Institute Berlin, Germany.Google Scholar
[73] Witzig J , Berthold T , Heinz S (2019b) A status report on conflict analysis in mixed integer nonlinear programming. Rousseau LM , Stergiou K , eds. Proc. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). Lecture Notes in Computer Science 11494 (Springer, Cham), 84-94.Crossref, Google Scholar · Zbl 07116687
[74] Witzig J , Beckenbach I , Eifler L , Fackeldey K , Gleixner A , Grever A , Weber M (2018) Mixed-integer programming for cycle detection in nonreversible Markov processes. Multiscale Model. Simulation 16(1):248-265.Google Scholar · Zbl 1391.60170
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.