Abstract
This paper provides a survey of recent progress and software for solving convex Mixed Integer Nonlinear Programs (MINLP)s, where the objective and constraints are defined by convex functions and integrality restrictions are imposed on a subset of the decision variables. Convex MINLPs have received sustained attention in recent years. By exploiting analogies to well-known techniques for solving Mixed Integer Linear Programs and incorporating these techniques into software, significant improvements have been made in the ability to solve these problems.
Supported by ANR grand BLAN06-1-138894.
The work of the second and third authors is supported by the US Department of Energy under grants DE-FG02-08ER25861 and DE-FG02-09ER25869, and the National Science Foundation under grant CCF-0830153.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Abhishek, S. Leyffer, and J.T. Linderoth, Feasibility pump heuristics for Mixed Integer Nonlinear Programs. Unpublished working paper, 2008.
, FilMINT: An outer-approximation-based solver for convex Mixed-Integer Nonlinear Programs, INFORMS Journal on Computing, 22, No. 4 (2010), pp. 555{567.
T. Achterberg and T. Berthold, Improving the feasibility pump, Technical Report ZIB-Report 05–42, Zuse Institute Berlin, September 2005.
T. Achterberg, T. Koch, and A. Martin, Branching rules revisited, Operations Research Letters, 33 (2004), pp. 42{54.
I. Akrotirianakis, I. Maros, and B. Rustem, An outer approximation based branch-and-cut algorithm for convex 0–1 MINLP problems, Optimization Methods and Software, 6 (2001), pp. 21{47.
D. Applegate, R. Bixby, V. Chv_atal, and W. Cook, On the solution of traveling salesman problems, in Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians, 1998, pp. 645{656.
A. Atamturk and V. Narayanan, Conic mixed integer rounding cuts, Mathematical Programming, 122 (2010), pp. 1{20.
E. Balas, Disjunctive programming, in Annals of Discrete Mathematics 5: Discrete Optimization, North Holland, 1979, pp. 3{51.
E. Balas, S. Ceria, and G. Corneujols, A lift-and-project cutting plane algorithm for ixed 0–1 programs, Mathematical Programming, 58 (1993), pp. 295{324.
E. Balas, S. Ceria, G. Cornu_ejols, and N. R. Natraj, Gomory cuts revisited, Operations Research Letters, 19 (1999), pp. 1{9.
E. Balas and M. Perregaard, Lift-and-project for mixed 0–1 programming: recent progress, Discrete Applied Mathematics, 123 (2002), pp. 129{154.
M.S. Bazaraa, H.D. Sherali, and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, New York, second ed., 1993.
E.M.L. Beale, Branch and bound methods for mathematical programming systems, in Discrete Optimization II, P.L. Hammer, E.L. Johnson, and B.H.Korte, eds., North Holland Publishing Co., 1979, pp. 201{219.
E.W.L. Beale and J.A. Tomlin, Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, in Proceedings of the 5th International Conference on Operations Research, J. Lawrence, ed., 1969, pp. 447{454.
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, SIAM, 2001. MPS/SIAM Series on Optimization.
J.F. Benders, Partitioning procedures for solving mixed variable programming problems, Numerische Mathematik, 4 (1962), pp. 238{252.
M. B_enichou, J.M. Gauthier, P. Girodet, G. Hentges, G. Ribi_ere, and O. Vincent, Experiments in Mixed-Integer Linear Programming, Mathematical Programming, 1 1971), pp. 76{94.
L. Bertacco, M. Fischetti, and A. Lodi, A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, 4 (2007), pp. 63{76.
T. Berthold, Primal Heuristics for Mixed Integer Programs, Master's thesis, Technische Universitat Berlin, 2006.
T. Berthold and A. Gleixner, Undercover - a primal heuristic for MINLP based on sub-mips generated by set covering, Tech. Rep. ZIB-Report 09–40, Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB), 2009.
D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), pp. 121{140.
R. Bixby and E. Rothberg, Progress in computational mixed integer programming. A look back from the other side of the tipping point, Annals of Operations Research, 149 (2007), pp. 37{41.
P. Bonami, Branching strategies and heuristics in branch-and-bound for convex MINLPs, November 2008. Presentation at IMA Hot Topics Workshop: Mixed-Integer Nonlinear Optimization: Algorithmic Advances and Applications.
P. Bonami, L.T. Biegler, A.R. Conn, G. Cornu_ejols, I.E. Grossmann, C.D. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya, and A. Wachter, An algorithmic framework for convex Mixed Integer Nonlinear Programs, Discrete Optimization, 5 (2008), pp. 186{204.
P. Bonami, G. Cornu_ejols, A. Lodi, and F. Margot, A feasibility pump for Mixed Integer Nonlinear Programs, Mathematical Programming, 119 (2009), pp. 331{352.
P. Bonami and J. Gonc_alves, Heuristics for convex mixed integer nonlinear programs, Computational Optimization and Applications. To appear DOI: 10.1007/s10589-010-9350-6.
R. Boorstyn and H. Frank, Large-scale network topological optimization, IEEE Transactions on Communications, 25 (1977), pp. 29{47.
B. Borchers and J.E. Mitchell, An improved branch and bound algorithm for Mixed Integer Nonlinear Programs, Computers & Operations Research, 21 (1994), pp. 359{368.
, A computational comparison of branch and bound and outer approximation algorithms for 0–1 Mixed Integer Nonlinear Programs, Computers & Operations Research, 24 (1997), pp. 699{701.
M.R. Bussieck and A. Drud, Sbb: A new solver for Mixed Integer Nonlinear Programming, talk, OR 2001, Section "Continuous Optimization", 2001.
M.R. Bussieck, A.S. Drud, and A. Meeraus, MINLPLib { a collection of test models for Mixed-Integer Nonlinear Programming, INFORMS Journal on Computing, 15 (2003).
R.H. Byrd, J. Nocedal, and R.A. Waltz, KNITRO: An integrated package for nonlinear optimization, in Large Scale Nonlinear Optimization, Springer Verlag, 2006, pp. 35{59.
I. Castillo, J. Westerlund, S. Emet, and T. Westerlund, Optimization of block layout deisgn problems with unequal areas: A comparison of milp and minlp optimization methods, Computers and Chemical Engineering, 30 (2005), pp. 54{69.
M.T. Cezik and G. Iyengar, Cuts for mixed 0–1 conic programming, Mathematical Programming, 104 (2005), pp. 179{202.
V. Chv_atal, Edmonds polytopes and a heirarchy of combinatorial problems, Discrete Mathematics, 4 (1973), pp. 305{337.
M. Conforti, G. Cornu_ejols, and G. Zambelli, Polyhedral approaches to Mixed Integer Linear Programming, in 50 Years of Integer Programming 1958–2008, M. Junger, T. Liebling, D. Naddef, W. Pulleyblank, G. Reinelt, G. Rinaldi, and L. Wolsey, eds., Springer, 2009.
G. Cornu_ejols, L. Liberti, and G. Nannicini, Improved strategies for branching on general disjunctions. To appear in Mathematical Programming A. DOI: 10.1007/s10107-009-0333-2.
R.J. Dakin, A tree search algorithm for mixed programming problems, Computer Journal, 8 (1965), pp. 250{255.
E. Danna, E. Rothberg, and C. LePape, Exploring relaxation induced neighborhoods to improve MIP solutions, Mathematical Programming, 102 (2005), pp. 71{90.
E. Dolan and J. Mor_e, Benchmarking optimization software with performance pro_les, Mathematical Programming, 91 (2002), pp. 201{213.
S. Drewes, Mixed Integer Second Order Cone Programming, PhD thesis, Technische Universitat Darmstadt, 2009.
A. S. Drud, CONOPT { a large-scale GRG code, ORSA Journal on Computing, 6 (1994), pp. 207{216.
M.A. Duran and I. Grossmann, An outer-approximation algorithm for a class of Mixed-Integer Nonlinear Programs, Mathematical Programming, 36 (1986), pp. 307{339.
J. Eckstein, Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5, SIAM Journal on Optimization, 4 (1994), pp. 794{
814.
S. Elhedhli, Service System Design with Immobile Servers, Stochastic Demand, and Congestion, Manufacturing & Service Operations Management, 8 (2006), pp. 92{97.
A. M. Eliceche, S. M. Corval_an, and P. Mart__nez, Environmental life cycle impact as a tool for process optimisation of a utility plant, Computers and Chemical Engineering, 31 (2007), pp. 648{656.
Fair Isaac Corporation, XPRESS-MP Reference Manual, 2009. Release 2009.
M. Fischetti, F. Glover, and A. Lodi, The feasibility pump, Mathematical Programming, 104 (2005), pp. 91{104.
M. Fischetti and A. Lodi, Local branching, Mathematical Programming, 98 (2003), pp. 23{47.
M. Fischetti and D. Salvagnin, Feasibility pump 2.0, Tech. Rep., University of Padova, 2008.
R. Fletcher and S. Leyffer, Solving Mixed Integer Nonlinear Programs by outer approximation, Mathematical Programming, 66 (1994), pp. 327{349.
, User manual for _lterSQP, 1998. University of Dundee Numerical Analysis Report NA-181.
A. Flores-Tlacuahuac and L.T. Biegler, Simultaneous mixed-integer dynamic optimization for integrated design and control, Computers and Chemical Engineering, 31 (2007), pp. 648{656.
J.J.H. Forrest, J.P.H. Hirst, and J.A. Tomlin, Practical solution of large scale mixed integer programming problems with UMPIRE, Management Science, 20 (1974), pp. 736{773.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
A. Geoffrion, Generalized Benders decomposition, Journal of Optimization Theory and Applications, 10 (1972), pp. 237{260.
P.E. Gill, W. Murray, and M.A. Saunders, SNOPT: An SQP algorithm for large{scale constrained optimization, SIAM Journal on Optimization, 12 (2002), pp. 979{1006.
R.E. Gomory, Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Monthly, 64 (1958), pp. 275{278.
, An algorithm for the mixed integer problem, Tech. Rep. RM-2597, The RAND Corporation, 1960.
I. Grossmann, J. Viswanathan, A.V.R. Raman, and E. Kalvelagen, GAMS/DICOPT: A discrete continuous optimization package, Math. Methods Appl. Sci, 11 (2001), pp. 649{664.
O. Gunluk, J. Lee, and R. Weismantel, MINLP strengthening for separaable convex quadratic transportation-cost u, Tech. Rep. RC24213 (W0703-042), IBM Research Division, March 2007.
O.K. Gupta and A. Ravindran, Branch and bound experiments in convex non- linear integer programming, Management Science, 31 (1985), pp. 1533{1546.
Gurobi Optimization, Gurobi Optimizer Reference Manual, 2009. Version 2.
I. Harjunkoski, R.Porn, and T. Westerlund, MINLP: Trim-loss problem, in Encyclopedia of Optimization, C.A. Floudas and P.M. Pardalos, eds., Springer, 2009, pp. 2190{2198.
J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms I: Fundamentals (Grundlehren Der Mathematischen Wis-senschaften), Springer, October 1993.
IBM, Using the CPLEX Callable Library, Version 12, 2009.
R. Jeroslow, There cannot be any algorithm for integer programming with quadratic constraints, Operations Research, 21 (1973), pp. 221{224.
N.J. Jobst, M.D. Horniman, C.A. Lucas, and G. Mitra, Computational as- pects of alternative portfolio selection models in the presence of discrete asset choice constraints, Quantitative Finance, 1 (2001), pp. 489{501.
M. Karamanov and G. Cornu_ejols, Branching on general disjunctions, tech. rep., Carnegie Mellon University, July 2005. Revised August 2009. Available at http://integer.tepper.cmu.edu.
J.E. Kelley, The cutting plane method for solving convex programs, Journal of SIAM, 8 (1960), pp. 703{712.
M. K_l_nc_, J. Linderoth, J. Luedtke, and A. Miller, Disjunctive strong branching inequalities for Mixed Integer Nonlinear Programs.
G.R. Kocis and I.E. Grossmann, Relaxation strategy for the structural optimization of process owheets, Industrial Engineering Chemical Research, 26 (1987), pp. 1869{1880.
C.D. Laird, L.T. Biegler, and B. van Bloemen Waanders, A mixed integer approach for obtaining unique solutions in source inversion of drinking water networks, Journal of Water Resources Planning and Management, Special Issue on Drinking Water Distribution Systems Security, 132 (2006), pp. 242{251.
A.H. Land and A.G. Doig, An automatic method for solving discrete programming problems, Econometrica, 28 (1960), pp. 497{520.
M. Lejeune, A uni_ed approach for cycle service levels, Tech. Rep. George Washington University, 2009. Available on Optimization Online http://www.optimization-online.org/DB HTML/2008/11/2144.html.
S. Leyffer, Deterministic Methods for Mixed Integer Nonlinear Programming, PhD thesis, University of Dundee, Dundee, Scotland, UK, 1993.
, User manual for MINLP-BB, 1998. University of Dundee.
, Integrating SQP and branch-and-bound for Mixed Integer Nonlinear Programming, Computational Optimization & Applications, 18 (2001), pp. 295{309.
, MacMINLP: Test problems for Mixed Integer Nonlinear Programming, 2003. http://www.mcs.anl.gov/~leyffer/macminlp.
, Nonlinear branch-and-bound revisited, August 2009. Presentation at 20th International Symposium on Mathematical Programming.
L. Liberti, Reformulations in mathematical programming: Symmetry, Mathematical Programming (2010). To appear.
J. Linderoth and T. Ralphs, Noncommercial software for Mixed-Integer Linear Programming, in Integer Programming: Theory and Practice, CRC Press Operations Research Series, 2005, pp. 253{303.
J.T. Linderoth and M.W.P. Savelsbergh, A computational study of search strategies in mixed integer programming, INFORMS Journal on Computing, 11 (1999), pp. 173{187.
A. Lodi, MIP computation and beyond, in 50 Years of Integer Programming 1958–2008, M. Junger, T. Liebling, D. Naddef, W. Pulleyblank, G. Reinelt, G. Rinaldi, and L. Wolsey, eds., Springer, 2009.
H. Marchand and L.A. Wolsey, Aggregation and mixed integer rounding to solve MIPs, Operations Research, 49 (2001), pp. 363{371.
F. Margot, Exploiting orbits in symmetric ILP, Mathematical Programming, Series B, 98 (2003), pp. 3{21.
R.D. McBride and J.S. Yormark, An implicit enumeration algorithm for quadratic integer programming, Management Science, 26 (1980), pp. 282{296.
Mosek ApS, 2009. www.mosek.com.
B. Murtagh and M. Saunders, MINOS 5.4 user's guide, Report SOL 83-20R, Department of Operations Research, Stanford University, 1993.
K.G. Murty and S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), pp. 117{ 129.
S. Nabal and L. Schrage, Modeling and solving nonlinear integer programming problems. Presented at Annual AIChE Meeting, Chicago, 1990.
G. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1988.
G.L. Nemhauser, M.W.P. Savelsbergh, and G.C. Sigismondi, MINTO, a Mixed INTeger Optimizer, Operations Research Letters, 15 (1994), pp. 47{58.
J. Nocedal and S.J. Wright, Numerical Optimization, Springer-Verlag, New York, second ed., 2006.
J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio, Orbital branching, Mathematical Programming, 126 (2011), pp. 147{178.
I. Quesada and I.E. Grossmann, An LP/NLP based branch{and{bound algorithm for convex MINLP optimization problems, Computers and Chemical Engineering, 16 (1992), pp. 937{947.
D.E. Ravemark and D.W.T. Rippin, Optimal design of a multi-product batch plant, Computers & Chemical Engineering, 22 (1998), pp. 177 { 183.
N. Sawaya, Reformulations, relaxations and cutting planes for generalized disjunctive programming, PhD thesis, Chemical Engineering Department, Carnegie Mellon University, 2006.
N. Sawaya, C.D. Laird, L.T. Biegler, P. Bonami, A.R. Conn, G. Cornu_ejols, I. E. Grossmann, J. Lee, A. Lodi, F. Margot, and A. Wachter, CMU-IBM open source MINLP project test set, 2006. http://egon.cheme.cmu.edu/ibm/page.htm.
A. Schrijver, Theory of Linear and Integer Programming, Wiley, Chichester, 1986.
R. Stubbs and S. Mehrotra, A branch-and-cut method for 0–1 mixed convex programming, Mathematical Programming, 86 (1999), pp. 515{532.
M. Turkay and I.E. Grossmann, Logic-based minlp algorithms for the optimal synthesis of process networks, Computers & Chemical Engineering, 20 (1996), pp. 959 { 978.
R.J. Vanderbei, LOQO: An interior point code for quadratic programming, Optimization Methods and Software (1998).
A. Vecchietti and I.E. Grossmann, LOGMIP: a disjunctive 0–1 non-linear optimizer for process system models, Computers and Chemical Engineering, 23 (1999), pp. 555 { 565.
J. Viswanathan and I.E. Grossmann, A combined penalty function and outer{approximation method for MINLP optimization, Computers and Chemical Engineering, 14 (1990), pp. 769{782.
A. Wachter, Some recent advanced in Mixed-Integer Nonlinear Programming, May 2008. Presentation at the SIAM Conference on Optimization.
A. Wachter and L.T. Biegler, On the implementation of a primal-dual interior point _lter line search algorithm for large-scale nonlinear programming, Mathematical Programming, 106 (2006), pp. 25{57.
R. Waltz, Current challenges in nonlinear optimization, 2007. Presentation at San Diego Supercomputer Center: CIEG Spring Orientation Workshop, available at www.sdsc.edu/us/training/workshops/2007sac_ studentworkshop/docs/SDSC07.ppt.
T. Westerlund, H.I. Harjunkoski, and R. Porn, An extended cutting plane method for solving a class of non-convex minlp problems, Computers and Chemical Engineering, 22 (1998), pp. 357{365.
T. Westerlund and K. Lundqvist, Alpha-ECP, version 5.101. an interactive minlp-solver based on the extended cutting plane method, in Updated version of Report 01-178-A, Process Design Laboratory, Abo Akademi Univeristy, 2005.
T. Westerlund and F. Pettersson, A cutting plane method for solving convex MINLP problems, Computers and Chemical Engineering, 19 (1995), pp. s131{s136.
T. Westerlund and R. Porn,. a cutting plane method for minimizing pseudconvex functions in the mixed integer case, Computers and Chemical Engineering, 24 (2000), pp. 2655{2665.
L.A. Wolsey, Integer Programming, John Wiley and Sons, New York, 1998.
Y. Zhu and T. Kuno, A disjunctive cutting-plane-based branch-and-cut algorithm for 0–1 mixed-integer convex nonlinear programs, Industrial and Engineering Chemistry Research, 45 (2006), pp. 187{196.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this paper
Cite this paper
Bonami, P., Kilinç, M., Linderoth, J. (2012). Algorithms and Software for Convex Mixed Integer Nonlinear Programs. In: Lee, J., Leyffer, S. (eds) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol 154. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1927-3_1
Download citation
DOI: https://doi.org/10.1007/978-1-4614-1927-3_1
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-1926-6
Online ISBN: 978-1-4614-1927-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)