×

zbMATH — the first resource for mathematics

Mixed integer nonlinear programming tools: an updated practical overview. (English) Zbl 1269.90067
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. Ph.D. thesis, Lehigh University.
[2] Abhishek, K., Leyffer, S., & Linderoth, J. (2010). FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs. INFORMS Journal on Computing, 22, 555–567. · Zbl 1243.90142 · doi:10.1287/ijoc.1090.0373
[3] Achterberg, T. (2007). Constraint integer programming. Ph.D. thesis, Technische Universität Berlin. · Zbl 1169.90414
[4] Adjiman, C., Androulakis, I., & Floudas, C. (1997). Global optimization of MINLP problems in process synthesis and design. Computers & Chemical Engineering, 21, 445–450.
[5] Adjiman, C., Androulakis, I., & Floudas, C. (2000). Global optimization of mixed-integer nonlinear problems. AIChE Journal, 46, 1769–1797. · doi:10.1002/aic.690460908
[6] Androulakis, I., Maranas, C., & Floudas, C. (1995). \(\alpha\)BB: a global optimization method for general constrained nonconvex problems. Journal of Global Optimization, 7, 337–363. · Zbl 0846.90087 · doi:10.1007/BF01099647
[7] Beale, E., & Tomlin, J. (1970). Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In J. Lawrence (Ed.), Proceedings of the Fifth International Conference on Operational Research: OR 69 (pp. 447–454). London: Tavistock.
[8] Belotti, P., Lee, J., Liberti, L., Margot, F., & Wächter, A. (2009). Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods & Software, 24, 597–634. · Zbl 1179.90237 · doi:10.1080/10556780903087124
[9] Benders, J. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 267–299. · Zbl 0109.38302 · doi:10.1007/BF01386316
[10] Berthold, T., Heinz, S., & Vigerske, S. (2012). Extending a CIP framework to solve MIQCPs. In J. Lee & S. Leyffer (Eds.), IMA volumes in mathematics and its applications: Vol. 154. Mixed-integer nonlinear optimization: algorithmic advances and applications (pp. 427–444). Berlin: Springer. · Zbl 1242.90120
[11] Bonami, P., & Gonçalves, J. (2008). Primal heuristics for mixed integer nonlinear programs (Tech. Rep.). IBM Research Report RC24639.
[12] Bonami, P., Forrest, J., Lee, J., & Wächter, A. (2007). Rapid development of an MINLP solver with COIN-OR. Optima, 75, 1–5.
[13] Bonami, P., Biegler, L., Conn, A., Cornuéjols, G., Grossmann, I., Laird, C., Lee, J., Lodi, A., Margot, F., Sawaya, N., & Wächter, A. (2008). An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5, 186–204. · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[14] Bonami, P., Cornuéjols, G., Lodi, A., & Margot, F. (2009). A feasibility pump for mixed integer nonlinear programs. Mathematical Programming, 119, 331–352. · Zbl 1163.90013 · doi:10.1007/s10107-008-0212-2
[15] Bongartz, I., Conn, A. R., Gould, N., & Toint, P. L. (1995). CUTE: constrained and unconstrained testing environment. ACM Transactions on Mathematical Software, 21, 123–160. doi: 10.1145/200979.201043 . · Zbl 0886.65058 · doi:10.1145/200979.201043
[16] Brooke, A., Kendrick, D., & Meeraus, A. (1992). GAMS: a user’s guide. URL citeseer.ist.psu.edu/brooke92gams.html .
[17] Bussieck, M., & Drud, A. SSB: a new solver for mixed integer nonlinear programming. In Recent advances in nonlinear mixed integer optimization, INFORMS Fall, Invited talk.
[18] Bussieck, M., & Vigerske, S. (2011). MINLP solver software. In J. Cochran (Ed.), Wiley encyclopedia of operations research and management science. New York: Wiley.
[19] CBC. URL https://projects.coin-or.org/Cbc .
[20] Conn, A., Scheinberg, K., & Vicente, L. (2008). MPS/SIAM book series on optimization. Introduction to derivative free optimization. Philadelphia: SIAM.
[21] Dakin, R. (1965). A tree-search algorithm for mixed integer programming problems. Computer Journal, 8(3), 250–255. doi: 10.1093/comjnl/8.3.250 . URL http://comjnl.oxfordjournals.org/content/8/3/250.abstract . · Zbl 0154.42004 · doi:10.1093/comjnl/8.3.250
[22] D’Ambrosio, C. (2010). Application-oriented mixed integer non-linear programming. 4OR, 8, 319–322. · Zbl 1205.90203 · doi:10.1007/s10288-010-0118-8
[23] D’Ambrosio, C., Frangioni, A., Liberti, L., & Lodi, A. (2010). A storm of feasibility pumps for nonconvex MINLP (Tech. Rep. OR/10/13). Università di Bologna. To appear in Mathematical Programming.
[24] D’Ambrosio, C., & Lodi, A. (2011). Mixed integer non-linear programming tools: a practical overview. 4OR: A. 4OR, 9, 329–349. · Zbl 1235.90101 · doi:10.1007/s10288-011-0181-9
[25] Duran, M., & Grossmann, I. (1986). An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming, 36, 307–339. · Zbl 0619.90052 · doi:10.1007/BF02592064
[26] Fourer, R., Gay, D., & Kernighan, B. (2003). AMPL: a modeling language for mathematical programming (2nd ed.). Monterey: Duxbury Press/Brooks/Cole Publishing Co. · Zbl 0701.90062
[27] Geoffrion, A. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10, 237–260. · Zbl 0229.90024 · doi:10.1007/BF00934810
[28] Grossmann, I. (2002). Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3, 227–252. · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[29] Gupta, O., & Ravindran, V. (1985). Branch and bound experiments in convex nonlinear integer programming. Management Science, 31, 1533–1546. · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[30] GUROBI. URL http://www.gurobi.com/ .
[31] IBM-CPLEX. URL http://www-01.ibm.com/software/integration/optimization/cplex/ . (v. 12.0).
[32] Jeroslow, R. (1973). There cannot be any algorithm for integer programming with quadratic constraints. Operations Research, 21, 221–224. · Zbl 0257.90029 · doi:10.1287/opre.21.1.221
[33] Kelley, J. E. Jr. (1960). The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8, 703–712. · Zbl 0098.12104 · doi:10.1137/0108053
[34] Kesavan, P., & Barto, P. (2000). Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems. Computers & Chemical Engineering, 24, 1361–1366. · doi:10.1016/S0098-1354(00)00421-X
[35] Kocis, G., & Grossmann, I. (1989). Computational experience with DICOPT solving MINLP problems in process systems engineering. Computers & Chemical Engineering, 13, 307–315. · doi:10.1016/0098-1354(89)85008-2
[36] Land, A., & Doig, A. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. URL http://www.jstor.org/stable/1910129 . · Zbl 0101.37004 · doi:10.2307/1910129
[37] Lee, J., & Leyffer, S. (Eds.) (2012). IMA volumes in mathematics and its applications: Vol. 154. Mixed integer nonlinear programming. Berlin: Springer.
[38] Leyffer, S. (1999). User manual for MINLP_BB (Tech. Rep.). University of Dundee.
[39] Leyffer, S. (2001). Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Computational Optimization and Applications, 18, 295–309. · Zbl 1009.90074 · doi:10.1023/A:1011241421041
[40] Leyffer, S., & Mahajan, A. (2011). Software for nonlinearly constrained optimization. New York: Wiley.
[41] Liberti, L. (2004a). Reformulation and convex relaxation techniques for global optimization. Ph.D. thesis, Imperial College, London, UK. · Zbl 1136.90442
[42] Liberti, L. (2004b). Reformulation and convex relaxation techniques for global optimization. 4OR, 2, 255–258. · Zbl 1136.90442 · doi:10.1007/s10288-004-0038-6
[43] Liberti, L. (2006). Writing global optimization software. In L. Liberti & N. Maculan (Eds.), Global optimization: from theory to implementation (pp. 211–262). Berlin: Springer. · Zbl 1100.90004
[44] Liberti, L., Cafieri, S., & Tarissan, F. (2009a). Reformulations in mathematical programming: a computational approach. In A. Abraham, A. Hassanien, & P. Siarry (Eds.), Studies in computational intelligence: Vol. 203. Foundations on computational intelligence, vol. 3 (pp. 153–234). New York: Springer.
[45] Liberti, L., Nannicini, G., & Mladenovic, N. (2009b). A good recipe for solving MINLPs. In V. Maniezzo, T. Stützle, & S. Voss (Eds.), Annals of information systems: Vol. 10. MATHEURISTICS: hybridizing metaheuristics and mathematical programming (pp. 231–244). Berlin: Springer.
[46] Linderoth, J., & Lodi, A. (2011). MILP software. In J. Cochran (Ed.), Wiley encyclopedia of operations research and management science (Vol. 5, pp. 3239–3248). New York: Wiley.
[47] Lodi, A. (2009). Mixed integer programming computation. In M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, & L. Wolsey (Eds.), 50 Years of integer programming 1958–2008: from the early years to the state-of-the-art (pp. 619–645). Berlin: Springer.
[48] Mangasarian, O. (1965). Pseudo-convex functions. Journal of the Society for Industrial and Applied Mathematics, 3, 281–290. · Zbl 0138.15702
[49] McCormick, G. (1976). Computability of global solutions to factorable nonconvex programs: Part I–convex underestimating problems. Mathematical Programming, 10, 147–175. · Zbl 0349.90100 · doi:10.1007/BF01580665
[50] Nannicini, G., & Belotti, P. (2011). Rounding based heuristics for nonconvex MINLPs (Tech. Rep.). Tepper, School of Business, Carnegie Mellon University. March. · Zbl 1257.90059
[51] Nemhauser, G., Savelsbergh, M., & Sigismondi, G. (1994). MINTO, a mixed INTeger optimizer. Operations Research Letters, 15, 47–585. · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[52] NEOS. URL www-neos.mcs.anl.gov/neos (v. 5.0). · Zbl 0923.65032
[53] Nocedal, J., & Wright, S. (2006). Springer series in operations research. Numerical optimization.
[54] Nowak, I. (2005). International series of numerical mathematics. Relaxation and decomposition methods for mixed integer nonlinear programming. Berlin: Birkhäuser. · Zbl 1089.90039
[55] Nowak, I., & Vigerske, S. (2008). LaGO–a (heuristic) branch and cut algorithm for nonconvex MINLPs. Central European Journal of Operations Research, 16, 127–138. · Zbl 1152.90665 · doi:10.1007/s10100-007-0051-x
[56] Quesada, I., & Grossmann, I. (1992). An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Computers & Chemical Engineering, 16, 937–947. · doi:10.1016/0098-1354(92)80028-8
[57] Ryoo, H., & Sahinidis, N. (1996). A branch-and-reduce approach to global optimization. Journal of Global Optimization, 8, 107–138. · Zbl 0856.90103 · doi:10.1007/BF00138689
[58] Sahinidis, N. (1996). BARON: a general purpose global optimization software package. Journal of Global Optimization, 8, 201–205. · Zbl 0856.90104 · doi:10.1007/BF00138693
[59] Schweiger, C., & Floudas, C. (1998a). MINOPT: a modeling language and algorithmic framework for linear, mixed-integer, nonlinear, dynamic, and mixed-integer nonlinear optimization. Princeton: Princeton University Press.
[60] Schweiger, C., & Floudas, C. (1998b). MINOPT: a software package for mixed-integer nonlinear optimization (3rd ed.).
[61] SCIP. URL http://scip.zib.de/scip.shtml .
[62] Smith, E., & Pantelides, C. (1999). A symbolic reformulation/spatial branch and bound algorithm for the global optimization of nonconvex MINLPs. Computers & Chemical Engineering, 23, 457–478. · doi:10.1016/S0098-1354(98)00286-5
[63] Tawarmalani, M., & Sahinidis, N. (2004). Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Mathematical Programming, 99, 563–591. · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[64] Vigerske, S. (2012). Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. PhD Thesis, Humboldt-Universität zu Berlin.
[65] Westerlund, T., & Pettersson, F. (1995). A cutting plane method for solving convex MINLP problems. Computers & Chemical Engineering, 19, S131–S136. · doi:10.1016/0098-1354(95)00164-W
[66] Westerlund, T., & Pörn, R. (2002). Solving pseudo-convex mixed integer problems by cutting plane techniques. Optimization and Engineering, 3, 253–280. · Zbl 1035.90051 · doi:10.1023/A:1021091110342
[67] Westerlund, T., Skrifvars, H., Harjunkoski, I., & Pörn, R. (1998). An extended cutting plane method for solving a class of non-convex MINLP problems. Computers & Chemical Engineering, 22, 357–365. · Zbl 0955.90095 · doi:10.1016/S0098-1354(97)00000-8
[68] XML-RPC. URL http://www.xmlrpc.com .
[69] XPRESS. URL http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx .
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.