×

Minotaur: a mixed-integer nonlinear optimization toolkit. (English) Zbl 1476.65099

Summary: We present a flexible framework for general mixed-integer nonlinear programming (MINLP), called Minotaur, that enables both algorithm exploration and structure exploitation without compromising computational efficiency. This paper documents the concepts and classes in our framework and shows that our implementations of standard MINLP techniques are efficient compared with other state-of-the-art solvers. We then describe structure-exploiting extensions that we implement in our framework and demonstrate their impact on solution times. Without a flexible framework that enables structure exploitation, finding global solutions to difficult nonconvex MINLP problems will remain out of reach for many applications.

MSC:

65K05 Numerical mathematical programming methods
90C11 Mixed integer programming
90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abhishek, K.; Leyffer, S.; Linderoth, JT, FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs, INFORMS J. Comput., 22, 555-567 (2010) · Zbl 1243.90142
[2] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41 (2009) · Zbl 1171.90476
[3] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 42-54 (2004) · Zbl 1076.90037
[4] Adjiman, CS; Androulakis, IP; Floudas, CA, A global optimization method, \( \alpha\) BB, for general twice-differentiable constrained NLPs-II. Implementation and computational results, Comput. Chem. Eng., 22, 1159-1179 (1998)
[5] Beale, E.W.L., Tomlin, J.A.: Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence, J. (ed.) Proceedings of the 5th International Conference on Operations Research, pp. 447-454 (1969)
[6] Belotti, P.: COUENNE: A user’s manual. Technical report. Lehigh University (2009)
[7] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, JT; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172
[8] Benson, HY, Mixed integer nonlinear programming using interior point methods, Optim. Methods Softw., 26, 6, 911-931 (2011) · Zbl 1229.90103
[9] Bonami, P.; Biegler, LT; Conn, AR; Cornuéjols, G.; Grossmann, IE; Laird, CD; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028
[10] Bonami, P.; Lee, J.; Leyffer, S.; Wächter, A., On branching rules for convex mixed-integer nonlinear optimization, J. Exp. Algorithm., 18, 2.6:2.1-2.6:2.31 (2013) · Zbl 1322.90052
[11] Brooke, A.; Kendrick, D.; Meeraus, A.; Raman, R., GAMS, A User’s Guide (1992), Fairfax: GAMS Development Corporation, Fairfax
[12] Bussieck, M.R., Drud, A.: SBB: a new solver for mixed integer nonlinear programming. Talk, OR 2001, Section Continuous Optimization (2001)
[13] Bussieck, MR; Drud, A.; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 1, 114-119 (2003) · Zbl 1238.90104
[14] Byrd, RH; Nocedal, J.; Richard, WA; Pillo, G.; Roma, M., KNITRO: an integrated package for nonlinear optimization, Large-Scale Nonlinear Optimization, Volume 83 of Nonconvex Optimization and Its Applications, 35-59 (2006), Berlin: Springer, Berlin · Zbl 1108.90004
[15] Christianson, B., Automatic Hessians by reverse accumulations, IMA J. Numer. Anal., 12, 2, 135-150 (1992) · Zbl 0754.65022
[16] CMU-IBM cyber-infrastructure for MINLP (2009). http://www.minlp.org/
[17] COIN-OR: Computational Infrastructure for Operations Research (2014). http://www.coin-or.org
[18] Dakin, RJ, A tree search algorithm for mixed programming problems, Comput. J., 8, 250-255 (1965) · Zbl 0154.42004
[19] Dolan, E.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[20] Drewes, S.: Mixed Integer Second Order Cone Programming. Ph.D. thesis. Technische Universität Darmstadt (2009) · Zbl 1176.90002
[21] Drewes, S.; Ulbrich, S., Subgradient based outer approximation for mixed integer second order cone programming, Mixed Integer Nonlinear Programming, Volume 154 of the IMA Volumes in Mathematics and Its Applications, 41-59 (2012), New York: Springer, New York · Zbl 1242.90130
[22] Duran, MA; Grossmann, I., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339 (1986) · Zbl 0619.90052
[23] Ferreau, HJ; Kirches, C.; Potschka, A.; Bock, HG; Diehl, M., qpOASES: a parametric active-set algorithm for quadratic programming, Math. Program. Comput., 6, 4, 327-363 (2014) · Zbl 1302.90146
[24] Fletcher, R., User Manual for BQPD (1995), Dundee: University of Dundee, Dundee
[25] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349 (1994) · Zbl 0833.90088
[26] Fletcher, R., Leyffer, S.: User Manual for filterSQP. University of Dundee Numerical Analysis Report NA-181 (1998)
[27] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 91, 239-270 (2002) · Zbl 1049.90088
[28] Floudas, CA, Deterministic Global Optimization: Theory, Algorithms and Applications (2000), Dordrecht: Kluwer Academic Publishers, Dordrecht
[29] Forrest, J.: CLP (2014). http://www.coin-or.org/
[30] Fourer, R.; Gay, DM; Kernighan, BW, AMPL: A Modeling Language for Mathematical Programming (1993), Cambridge: The Scientific Press, Cambridge · Zbl 0701.90062
[31] Frangioni, A.; Furini, F.; Gentile, C., Approximated perspective relaxations: a project and lift approach, Comput. Optim. Appl., 63, 705-735 (2016) · Zbl 1362.90301
[32] Frangioni, A.; Gentile, C., Perspective cuts for a class of convex 0-1 mixed integer programs, Math. Program., 106, 225-236 (2006) · Zbl 1134.90447
[33] Frangioni, A.; Gentile, C., SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Oper. Res. Lett., 35, 181-185 (2007) · Zbl 1149.90379
[34] Frangioni, A.; Gentile, C., A computational comparison of reformulations of the perspective relaxation: SOCP vs cutting planes, Oper. Res. Lett., 37, 3, 206-210 (2009) · Zbl 1167.90604
[35] Furman, K., Grossmann, I., Sawaya, N.: An exact MINLP formulation for nonlinear disjunctive programs based on the convex hull. In: Presented at the 20th International Symposium on Mathematical Programming, Chicago, IL (2009)
[36] Gay, DM; Berz, M.; Bischof, C.; Corliss, G.; Griewank, A., More AD of nonlinear AMPL models: computing Hessian information and exploiting partial separability, Computational Differentiation Techniques Applications and Tools (1996), Philadelphia: SIAM, Philadelphia
[37] Gebremedhin, AH; Tarafdar, A.; Pothen, A.; Walther, A., Efficient computation of sparse Hessians using coloring and automatic differentiation, INFORMS J. Comput., 21, 2, 209-223 (2009) · Zbl 1243.65071
[38] Geoffrion, AM, Generalized Benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024
[39] Gould, N.; Scott, J., A note on performance profiles for benchmarking software, ACM Trans. Math. Softw., 43, 2, 1-5 (2016) · Zbl 1369.65202
[40] Griewank, A.; Walther, A., Evaluating Derivatives Principles and Techniques of Algorithmic Differentiation (2008), Philadelphia: SIAM, Philadelphia · Zbl 1159.65026
[41] Grossmann, IE; Kravanja, Z.; Conn, AR; Biegler, LT; Coleman, TF; Santosa, FN, Mixed-integer nonlinear programming: a survey of algorithms and applications, Large-Scale Optimization with Applications, Part II: Optimal Design and Control (1997), New York: Springer, New York
[42] Günlük, O., Linderoth, J.: Perspective relaxation of mixed integer nonlinear programs with indicator variables. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008: The Thirteenth Conference on Integer Programming and Combinatorial Optimization, vol. 5035, pp. 1-16 (2008) · Zbl 1143.90364
[43] Günlük, O.; Linderoth, JT, Perspective relaxation of mixed integer nonlinear programs with indicator variables, Math. Program. Ser. B, 104, 186-203 (2010) · Zbl 1229.90106
[44] Günlük, O.; Linderoth, JT, Perspective reformulation and applications, IMA Vol., 154, 61-92 (2012) · Zbl 1242.90134
[45] Gupta, OK; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 1533-1546 (1985) · Zbl 0591.90065
[46] Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual, Version 5.6 (2014)
[47] Hart, WE; Watson, J-P; Woodruff, DL, Pyomo: modeling and solving mathematical programs in Python, Math. Program. Comput., 3, 219-260 (2011)
[48] IBM Corp. IBM ILOG CPLEX V12.6: User’s Manual for CPLEX (2014)
[49] Jeroslow, RG, There cannot be any algorithm for integer programming with quadratic constraints, Oper. Res., 21, 1, 221-224 (1973) · Zbl 0257.90029
[50] Kannan, R.; Monma, CL; Henn, R.; Korte, B.; Oettli, W., On the computational complexity of integer programming problems, Optimization and Operations Research, Volume 157 of Lecture Notes in Economics and Mathematical Systems, 161-172 (1978), Berlin: Springer, Berlin
[51] Land, AH; Doig, AG, An automatic method for solving discrete programming problems, Econometrica, 28, 497-520 (1960) · Zbl 0101.37004
[52] Lasserre, J.; Aardal, K.; Gerards, AMH, An explicit exact SDP relaxation for nonlinear 0-1 programs, Integer Programming and Combinatorial Optimization 2001, Lecture Notes in Computer Science, 293-303 (2001), Berlin: Springer, Berlin · Zbl 1010.90515
[53] Lasserre, J., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[54] Laurent, M., A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 3, 470-496 (2003) · Zbl 1082.90084
[55] Leyffer, S., User Manual for MINLP-BB (1998), Dundee: University of Dundee, Dundee
[56] Leyffer, S.: Mixed-Integer PDE-Constrained Optimization. Technical report. Argonne (2015)
[57] Leyffer, S., Linderoth, J.T., Luedtke, J., Miller, A., Munson T.: Applications and algorithms for mixed integer nonlinear programming. In: Journal of Physics: Conference Series, SciDAC 2009, vol. 180, pp. 012014 (2009)
[58] Mahajan, A., Leyffer, S., Kirches, C.: Solving convex mixed-integer nonlinear programs by QP-diving. Preprint ANL/MCS-P1801-101. Argonne National Laboratory (2010)
[59] Mahajan, A., Leyffer, S., Kirches, C.: Solving mixed-integer nonlinear programs by QP-diving. Preprint ANL/MCS-2071-0312. Argonne National Laboratory, Mathematics and Computer Science Division (2012)
[60] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175 (1976) · Zbl 0349.90100
[61] Misener, R.; Floudas, CA, GloMIQO: global mixed-integer quadratic optimizer, J. Glob. Optim., 5, 1-48 (2012) · Zbl 1272.90034
[62] Misener, R.; Floudas, CA, ANTIGONE: algorithms for coNTinuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526 (2014) · Zbl 1301.90063
[63] Neumaier, A., Complete search in continuous global optimization and constraint satisfaction, Acta Numer., 13, 271-369 (2004) · Zbl 1113.90124
[64] Nocedal, J.; Wright, SJ, Numerical Optimization (1999), New York: Springer, New York · Zbl 0930.65067
[65] Quesada, I.; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947 (1992)
[66] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 552-566 (1995)
[67] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205 (1996) · Zbl 0856.90104
[68] Savelsbergh, MWP, Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 445-454 (1994) · Zbl 0814.90093
[69] Schichl, H.; Alt, R.; Frommer, A.; Baker Kearfott, R.; Luther, W., Global optimization in the COCONUT project, Numerical Software with Result Verification, Volume 2991 of Lecture Notes in Computer Science, 243-249 (2004), Berlin: Springer, Berlin · Zbl 1126.65318
[70] Still, C.; Westerlund, T., Solving convex MINLP optimization problems using a sequential cutting plane algorithm, Comput. Optim. Appl., 34, 1, 63-83 (2006) · Zbl 1111.90087
[71] Tawarmalani, M.; Sahinidis, NV, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications (2002), Boston: Kluwer Academic Publishers, Boston · Zbl 1031.90022
[72] Van Roy, TJ, Cross decomposition for mixed integer programming, Math. Program., 25, 145-163 (1983)
[73] Vigerske, S.: MINLPLib 2. In: Proceedings of the XII Global Optimization Workshop: Mathematical and Applied Global Optimization, pp. 137-140 (2014)
[74] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim. Methods Softw., 33, 3, 563-593 (2018) · Zbl 1398.90112
[75] Viswanathan, J.; Grossmann, IE, A combined penalty function and outer-approximation method for MINLP optimization, Comput. Chem. Eng., 14, 7, 769-782 (1990)
[76] Wächter, A.; Biegler, LT, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[77] Westerlund, T., Lundqvist, K.: Alpha-ECP, version 5.01: an interactive MINLP-solver based on the extended cutting plane method. Technical Report 01-178-A. Process Design Laboratory at Åbo University (2001)
[78] Westerlund, T.; Pettersson, F., A cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136 (1995)
[79] Ziena Optimization. KNITRO Documentation (2012)
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.