×

zbMATH — the first resource for mathematics

An outer-inner approximation for separable mixed-integer nonlinear programs. (English) Zbl 1356.90091
Summary: A common structure in convex mixed-integer nonlinear programs (MINLPs) is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. As a side result, we exhibit a simple example where a classical implementation of the outer approximation would take an exponential number of iterations, whereas it is easily solved with our modifications. These methods have been implemented in the open source solver Bonmin and are available for download from the Computational Infrastructure for Operations Research project website. We test the effectiveness of the approach on three real-world applications and on a larger set of models from an MINLP benchmark library. Finally, we show how the techniques can be extended to perspective formulations of several problems. The proposed tools lead to an important reduction in computing time on most tested instances.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhishek K, Leyffer S, Linderoth J (2010) FilMINT: An outer approximation-based solver for convex mixed-integer nonlinear programs. INFORMS J. Comput. 22(4):555-567. Link · Zbl 1243.90142
[2] Ben Ameur W, Ouorou A (2006) Mathematical models of the delay constrained routing problem. Algorithmic Oper. Res. 1(2):94-103. · Zbl 1186.90116
[3] Bonami P, Kılınç M, Linderoth J (2012) Algorithms and software for convex mixed integer nonlinear programs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and Its Applications, Vol. 154 (Springer, New York), 1-39. CrossRef · Zbl 1242.90121
[4] Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, Lee J (2008) An algorithmic framework for convex mixed-integer nonlinear programs. Discrete Optim. 5(2):186-204. CrossRef · Zbl 1151.90028
[5] Castillo I, Westerlund J, Emet S, Westerlund T (2005) Optimization of block layout deisgn problems with unequal areas: A comparison of MILP and MINLP optimization methods. Comput. Chemical Engrg. 30(1):54-69. CrossRef
[6] Duran MA, Grossmann I (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36(3):307-339. CrossRef · Zbl 0619.90052
[7] Elhedhli S (2006) Service system design with immobile servers, stochastic demand, and congestion. Manufacturing Service Oper. Management 8:92-97. Link
[8] Fletcher R, Leyffer S (1994) Solving mixed-integer nonlinear programs by outer approximation. Math. Programming 66:327-349. CrossRef · Zbl 0833.90088
[9] Fourer R, Gay DM, Kernighan BW (1993) AMPL: A Modeling Language for Mathematical Programming (Duxbury Press, Pacific Grove, CA).
[10] Frangioni A, Gentile C (2006) Perspective cuts for a class of convex 0-1 mixed-integer programs. Math. Programming 106:225-236. CrossRef · Zbl 1134.90447
[11] Grossmann I, Viswanathan J, Vecchietti A, Raman R, Kalvelagen E (2001) GAMS/DICOPT: A discrete continuous optimization package. Math. Methods Appl. Sci. 11:649-664.
[12] Günlük O, Linderoth J (2010) Perspective relaxation of mixed-integer nonlinear programs with indicator variables. Math. Programming 124:183-205. CrossRef · Zbl 1229.90106
[13] Günlük O, Lee J, Weismantel R (2007) MINLP strengthening for separable convex quadratic transportation-cost UFL. Technical Report RC24213 (W0703-042), IBM Research Division, T.J. Watson Research Center, Cambridge, MA.
[14] Harjunkoski I, Pörn R, Westerlund T (2009) MINLP: Trim-loss problem. Floudas CA, Pardalos PM, eds. Encyclopedia of Optimization (Springer, New York), 2190-2198. CrossRef
[15] Hijazi H (2010) Mixed-integer nonlinear optimization approaches for network design in telecommunications. Ph.D. thesis, Aix-Marseille Université, Marseille, France.
[16] Hijazi H, Bonami P, Cornuéjols G, Ouorou A (2012) Mixed-integer nonlinear programs featuring on/off constraints. Comput. Optim. Appl. 52:537-558. CrossRef · Zbl 1250.90058
[17] Lougee-Heimer R (2003) The common optimization interface for operations research. IBM J. Res. Development 47:57-66. CrossRef
[18] 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. CrossRef
[19] Ravemark DE, Rippin DWT (1998) Optimal design of a multi-product batch plant. Comput. Chemical Engrg. 22(1-2):177-183. CrossRef
[20] Sawaya N (2006) Reformulations, relaxations and cutting planes for generalized disjunctive programming. Ph.D. thesis, Chemical Engineering Department, Carnegie Mellon University, Pittsburgh, PA.
[21] Sawaya N, Laird CD, Biegler LT, Bonami P, Conn AR, Cornuéjols G, Grossmann IE (2006) CMU-IBM open source MINLP project test set. Accessed December 2011, http://egon.cheme.cmu.edu/ibm/page.htm.
[22] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225-249. CrossRef · Zbl 1099.90047
[23] Türkay M, Grossmann IE (1996) Logic-based MINLP algorithms for the optimal synthesis of process networks. Comput. Chemical Engrg. 20(8):959-978. CrossRef
[24] Vecchietti A, Grossmann IE (1999) LOGMIP: A disjunctive 0-1 non-linear optimizer for process system models. Comput. Chemical Engrg. 23(4-5):555-565. CrossRef
[25] Wächter A, Biegler LT (2006) On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25-57. CrossRef · Zbl 1134.90542
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.