×

zbMATH — the first resource for mathematics

Mixed integer nonlinear programming tools: a practical overview. (English) Zbl 1235.90101
Summary: We present a review of available tools for solving mixed integer nonlinear programming problems. Our aim is to give the reader a flavor of the difficulties one could face and to discuss the tools one could use to try to overcome such difficulties.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhishek K (2008) Topics in mixed integer nonlinear programming. PhD thesis, Lehigh University
[2] Abhishek K, Leyffer S, Linderoth JT (2010) FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs. INFORMS J Comput 22: 555–567 · Zbl 1243.90142 · doi:10.1287/ijoc.1090.0373
[3] Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universität Berlin · Zbl 1169.90414
[4] Adjiman CS, Androulakis IP, Floudas CA (1997) Global optimization of MINLP problems in process synthesis and design. Comput Chem Eng 21: 445–450 · doi:10.1016/S0097-8485(97)00020-X
[5] Adjiman CS, Androulakis IP, Floudas CA (2000) Global optimization of mixed-integer nonlinear problems. AIChE J 46: 1769–1797 · doi:10.1002/aic.690460908
[6] Androulakis IP, Maranas CD, Floudas CA (1995) \(\alpha\)BB: a global optimization method for general constrained nonconvex problems. J Glob Optim 7: 337–363 · Zbl 0846.90087 · doi:10.1007/BF01099647
[7] Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence J (eds) OR 69. Proceedings of the fifth international conference on operational research. Tavistock Publications, pp. 447–454
[8] Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw 24: 597–634 · Zbl 1179.90237 · doi:10.1080/10556780903087124
[9] Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4: 267–299
[10] Bonami P, Gonçalves JPM (2008) Primal heuristics for mixed integer nonlinear programs. Technical report, IBM Research Report RC24639
[11] Bonami P, Forrest J, Lee J, Wächter A (2007) Rapid development of an MINLP solver with COIN-OR. Optima 75: 1–5
[12] Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, Lee J, Lodi A, Margot F, Sawaya N, Wächter A (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discret Optim 5: 186–204 · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[13] Bonami P, Cornuéjols G, Lodi A, Margot F (2009) A feasibility pump for mixed integer nonlinear programs. Math Program 119: 331–352 · Zbl 1163.90013 · doi:10.1007/s10107-008-0212-2
[14] Bongartz I, Conn AR, Gould N, Toint PL (1995) CUTE: constrained and unconstrained testing environment. ACM Trans Math Softw 21: 123–160 · Zbl 0886.65058 · doi:10.1145/200979.201043
[15] Brooke A, Kendrick D, Meeraus A (1992) GAMS: a user’s guide
[16] Bussieck MR, Drud A (2001) SBB: a new solver for mixed integer nonlinear programming. In: Recent advances in nonlinear mixed integer optimization, INFORMS Fall, Invited talk
[17] Bussieck MR, Vigerske S (2011) MINLP solver software. In: Cochran JJ (eds) Wiley encyclopedia of operations research and management science. Wiley, New York
[18] Conn AR, Scheinberg K, Vicente LN (2008) Introduction to derivative free optimization. MPS/SIAM book series on optimization. SIAM, Philadelphia
[19] Dakin RJ (1965) A tree-search algorithm for mixed integer programming problems. Comp J 8(3): 250–255 · Zbl 0154.42004 · doi:10.1093/comjnl/8.3.250
[20] D’Ambrosio C (2010) Application-oriented mixed integer non-linear programming. 4OR Q J Oper Res 8: 319–322 · Zbl 1205.90203 · doi:10.1007/s10288-010-0118-8
[21] D’Ambrosio C, Frangioni A, Liberti L, Lodi A (2010) A storm of feasibility pumps for nonconvex MINLP. Technical Report OR/10/13, Università di Bologna. To appear in mathematical programming · Zbl 1257.90056
[22] Duran M, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math Program 36: 307–339 · Zbl 0619.90052 · doi:10.1007/BF02592064
[23] Fourer R, Gay DM, Kernighan BW (2003) AMPL: a modeling language for mathematical programming. 2nd edn. Duxbury Press, Pacific Grove
[24] Geoffrion AM (1972) Generalized Benders decomposition. J Optim Theory Appl 10: 237–260 · Zbl 0229.90024 · doi:10.1007/BF00934810
[25] Grossmann IE (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim Eng 3: 227–252 · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[26] Gupta OK, Ravindran V (1985) Branch and bound experiments in convex nonlinear integer programming. Manag Sci 31: 1533–1546 · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[27] Jeroslow R (1973) There cannot be any algorithm for integer programming with quadratic constraints. Oper Res 21: 221–224 · Zbl 0257.90029 · doi:10.1287/opre.21.1.221
[28] Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J SIAM 8: 703–712
[29] Kesavan P, Barto PI (2000) Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems. Comput Chem Eng 24: 1361–1366 · doi:10.1016/S0098-1354(00)00421-X
[30] Kocis GR, Grossmann IE (1989) Computational experience with DICOPT solving MINLP problems in process systems engineering. Comput Chem Eng 13: 307–315 · doi:10.1016/0098-1354(89)85008-2
[31] Land AH, Doig AG (1960) An automatic method of solving discrete programming problems. Econometrica 28(3): 497–520 · Zbl 0101.37004 · doi:10.2307/1910129
[32] Leyffer S (1999) User manual for $${{\(\backslash\)tt MINLP\(\backslash\)_BB}}$$ . Technical report. University of Dundee
[33] Leyffer S (2001) Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Comput Optim Appl 18: 295–309 · Zbl 1009.90074 · doi:10.1023/A:1011241421041
[34] Leyffer S, Mahajan A (2011) Software for nonlinearly constrained optimization. Wiley, New York
[35] Liberti L (2004a) Reformulation and convex relaxation techniques for global optimization. PhD thesis, Imperial College London, UK · Zbl 1136.90442
[36] Liberti L (2004b) Reformulation and convex relaxation techniques for global optimization. 4OR Q J Oper Res 2: 255–258 · Zbl 1136.90442 · doi:10.1007/s10288-004-0038-6
[37] Liberti L (2006) Writing global optimization software. In: Liberti L, Maculan N (eds) Global optimization: from theory to implementation. Springer, Berlin, pp 211–262 · Zbl 1100.90004
[38] Liberti L, Cafieri S, Tarissan F (2009a) Reformulations in mathematical programming: a computational approach. In: Abraham A, Hassanien AE, Siarry P (eds) Foundations on computational intelligence, studies in computational intelligence, vol 203. Springer, New York, pp 153–234
[39] Liberti L, Nannicini G, Mladenovic N (2009b) A good recipe for solving MINLPs. In: Maniezzo V, Stützle T, Voss S (eds) Matheuristics: hybridizing metaheuristics and mathematical programming, volume 10 of annals of information systems. Springer, Berlin, pp 231–244
[40] Linderoth JT, Lodi A (2011) MILP software. In: Cochran JJ (eds) Wiley encyclopedia of operations research and management science, vol 5. Wiley, New York, pp 3239–3248
[41] Lodi A (2009) Mixed integer programming computation. In: Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (eds) 50 years of integer programming 1958–2008: from the early years to the state-of-the-art. Springer, Berlin, pp 619–645
[42] Mangasarian OL (1965) Pseudo-convex functions. J Soc Ind Appl Math 3: 281–290 · Zbl 0138.15702 · doi:10.1137/0303020
[43] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I–convex underestimating problems. Math Program 10: 147–175 · Zbl 0349.90100 · doi:10.1007/BF01580665
[44] Nannicini G, Belotti P (2011) Rounding based heuristics for nonconvex MINLPs. Technical report, Tepper School of Business. Carnegie Mellon University · Zbl 1257.90059
[45] Nemhauser GL, Savelsbergh MWP, Sigismondi GS (1994) MINTO, a mixed INTeger optimizer. Oper Res Lett 15: 47–585 · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[46] Nocedal J, Wright SJ (2006) Numerical optimization. Springer Series in operations research · Zbl 1104.65059
[47] Nowak I (2005) Relaxation and decomposition methods for mixed integer nonlinear programming, International series of numerical mathematics. Birkhäuser Verlag, Basel · Zbl 1089.90039
[48] Nowak I, Vigerske S (2008) LaGO–a (heuristic) branch and cut algorithm for nonconvex MINLPs. Central Eur J Oper Res 16: 127–138 · Zbl 1152.90665 · doi:10.1007/s10100-007-0051-x
[49] Quesada I, Grossmann IE (1992) An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput Chem Eng 16: 937–947 · doi:10.1016/0098-1354(92)80028-8
[50] Ryoo H, Sahinidis NV (1996) A branch-and-reduce approach to global optimization. J Glob Optim 8: 107–138 · Zbl 0856.90103 · doi:10.1007/BF00138689
[51] Sahinidis NV (1996) BARON: a general purpose global optimization software package. J Glob Optim 8: 201–205 · Zbl 0856.90104 · doi:10.1007/BF00138693
[52] Schweiger CA, Floudas CA (1998a) MINOPT: a modeling language and algorithmic framework for linear, mixed-integer, nonlinear, dynamic, and mixed-integer nonlinear optimization. Princeton University, Princeton
[53] Schweiger CA, Floudas CA (1998b) MINOPT: a software package for mixed-integer nonlinear optimization, 3rd edn
[54] Smith EMB, Pantelides CC (1999) A symbolic reformulation/spatial branch and bound algorithm for the global optimization of nonconvex MINLPs. Comput Chem Eng 23: 457–478 · doi:10.1016/S0098-1354(98)00286-5
[55] Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math Program 99: 563–591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[56] Westerlund T, Pettersson F (1995) A cutting plane method for solving convex MINLP problems. Comput Chem Eng 19: S131–S136 · doi:10.1016/0098-1354(95)00164-W
[57] Westerlund T, Pörn R (2002) Solving pseudo-convex mixed integer problems by cutting plane techniques. Optim Eng 3: 253–280 · Zbl 1035.90051 · doi:10.1023/A:1021091110342
[58] Westerlund T, Skrifvars H, Harjunkoski I, Pörn R (1998) An extended cutting plane method for solving a class of non-convex MINLP problems. Comput Chem Eng 22: 357–365 · Zbl 0955.90095 · doi:10.1016/S0098-1354(97)00000-8
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.