×

zbMATH — the first resource for mathematics

Lift-and-project cuts for convex mixed integer nonlinear programs. (English) Zbl 1387.90159
Summary: We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
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] Atamtürk, A; Narayanan, V, Conic mixed integer rounding cuts, Math. Program., 122, 1-20, (2010) · Zbl 1184.90112
[3] Balas, E, Disjunctive programming, Ann. Discret. Math., 5, 3-51, (1979) · Zbl 0409.90061
[4] Balas, E, A modified lift-and-project procedure, Math. Program., 79, 19-31, (1997) · Zbl 0887.90127
[5] Balas, E; Ceria, S; Cornuejols, G, Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Manag. Sci., 42, 1229-1246, (1996) · Zbl 0880.90105
[6] Balas, E; Jeroslow, RG, Strengthening cuts for mixed integer programs, Eur. J. Oper. Res., 4, 224-234, (1980) · Zbl 0439.90064
[7] Balas, E; Perregaard, M, A precise correspondence between lift-and-project cuts, simple disjunctive cuts, Math. Program. Ser. B, 94, 221-245, (2003) · Zbl 1030.90068
[8] Balas, E; Saxena, A, Optimizing over the split closure, Math. Program., 113, 219-240, (2008) · Zbl 1135.90030
[9] Bertsekas, D., Gallager, R.: Data Networks, 2nd edn. Prentice-Hall Inc, Upper Saddle River (1992) · Zbl 0734.68006
[10] Bodur, M; Dash, S; Günlük, O, Cutting planes from extended LP formulations, Math. Program., (2016) · Zbl 1356.90089
[11] Bodur, M., Dash, S., Günlük, O., Luedtke, J.: Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse. http://www.optimization-online.org/DB_HTML/2014/03/4263.html (2014) · Zbl 1364.90220
[12] Bonami, P; Günlük, O (ed.); Woeginger, G (ed.), Lift-and-project cuts for mixed integer convex programs, No. 6655, 52-64, (2011), Berlin · Zbl 1339.90243
[13] Bonami, P, On optimizing over lift-and-project closures, Math. Program. Comput., 4, 151-179, (2012) · Zbl 1275.90042
[14] Bonami, P; Minoux, M, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Discret. Optim., 2, 288-307, (2005) · Zbl 1172.90450
[15] Bonami, P., Tramontani, A.: Advances in CPLEX for mixed integer nonlinear optimization. International Symposium on Mathematical Programming. Pittsburgh. PA, USA (2015) · Zbl 0880.90105
[16] Boorstyn, R; Frank, H, Large-scale network topological optimization, IEEE Trans. Commun., 25, 29-47, (1977) · Zbl 0361.94044
[17] Borchers, B; Mitchell, JE, An improved branch and bound algorithm for mixed integer nonlinear programs, Comput. Oper. Res., 21, 359-368, (1994) · Zbl 0797.90069
[18] Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114-119 (2003) · Zbl 1238.90104
[19] Castillo, I; Westerlund, J; Emet, S; Westerlund, T, Optimization of block layout design problems with unequal areas: a comparison of MILP and MINLP optimization methods, Comput. Chem. Eng., 30, 54-69, (2005)
[20] Ceria, S; Soares, J, Convex programming for disjunctive optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049
[21] Cezik, MT; Iyengar, G, Cuts for mixed 0-1 conic programming, Math. Program., 104, 179-202, (2005) · Zbl 1159.90457
[22] Conforti, M; Cornuéjols, G; Zambelli, G; Jünger, M (ed.); Liebling, T (ed.); Naddef, D (ed.); Pulleyblank, W (ed.); Reinelt, G (ed.); Rinaldi, G (ed.); Wolsey, L (ed.), Polyhedral approaches to mixed integer linear programming, 343-385, (2009), New York
[23] Cornuéjols, G, Valid inequalities for mixed integer linear programs, Math. Program. Ser. B, 112, 3-44, (2008) · Zbl 1278.90266
[24] Dash, S; Günlük, O; Lodi, A, MIR closures of polyhedral sets, Math. Program., 121, 33-60, (2010) · Zbl 1184.90107
[25] Dash, S; Günlük, O; Vielma, J, Computational experiments with cross and crooked cross cuts, INFORMS J. Comput., 26, 780-797, (2014) · Zbl 1304.90225
[26] Dolan, E; Moré, J, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[27] Drewes, S.: Mixed Integer Second Order Cone Programming. Ph.D. thesis, Technische Universität Darmstadt (2009) · Zbl 1176.90002
[28] 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
[29] Elhedhli, S, Service system design with immobile servers, stochastic demand, and congestion, Manuf. Serv. Oper. Manag., 8, 92-97, (2006)
[30] Fischetti, M; Lodi, A, Optimizing over the first chvátal closure, Math. Program. Ser. B, 110, 3-20, (2007) · Zbl 1192.90125
[31] Fischetti, M; Lodi, A; Tramontani, A, On the separation of disjunctive cuts, Math. Program., 128, 205-230, (2011) · Zbl 1218.90125
[32] Fletcher, R., Leyffer, S.: User Manual for FilterSQP. University of Dundee Numerical Analysis Report NA-181 (1998) · Zbl 1192.90125
[33] 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
[34] Gomory, R.E.: An Algorithm for the Mixed Integer Problem. Technical Report RM-2597, The RAND Corporation (1960) · Zbl 1184.90112
[35] Günlük, O., Lee, J., Weismantel, R.: MINLP strengthening for separable convex quadratic transportation-cost UFL. Technical Report RC24213 (W0703-042), IBM Research Division (2007) · Zbl 0619.90052
[36] Günlük, O; Linderoth, J; Lodi, A (ed.); Panconesi, A (ed.); Rinaldi, G (ed.), Perspective relaxation of mixed integer nonlinear programs with indicator variables, No. 5035, 1-16, (2008), New York · Zbl 1143.90364
[37] Harjunkoski, I; Westerlund, T; Porn, R; Skrifvars, H, Different transformations for solving non-convex trim loss problems by MINLP, Eur. J. Oper. Res., 105, 594-603, (1998) · Zbl 0955.90095
[38] Hijazi, H; Bonami, P; Ouorou, A, An outer-inner approximation for separable mixed-integer nonlinear programs, INFORMS J. Comput., 26, 31-44, (2014) · Zbl 1356.90091
[39] Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals (Grundlehren Der Mathematischen Wissenschaften). Springer, New York (1993) · Zbl 0795.49001
[40] IBM: Using the CPLEX Callable Library, Version 12 (2009)
[41] Kelley, J, The cutting-plane method for solving convex programs, J. SIAM, 8, 703-712, (1960) · Zbl 0098.12104
[42] Kılınç, M., Linderoth, J., Luedtke, J.: Effective Separation of Disjunctive Cuts for Convex Mixed Integer Nonlinear Programs. Technical Report 1681, Computer Sciences Department, University of Wisconsin-Madison (2010) · Zbl 1243.90142
[43] Kılınç, M.R.: Disjunctive Cutting Planes and Algorithms for Convex Mixed Integer Nonlinear Programming. Ph.D. thesis, University of Wisconsin-Madison (2011) · Zbl 0806.90095
[44] Leyffer, S.: MacMINLP: Test Problems for Mixed Integer Nonlinear Programming. http://www-unix.mcs.anl.gov/ leyffer/macminlp (2003) · Zbl 0954.90049
[45] Modaresi, S; Kılınç, M; Vielma, JP, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Math. Program., 155, 575-611, (2016) · Zbl 1358.90078
[46] Modaresi, S; Kılınç, MR; Vielma, JP, Split cuts and extended formulations for mixed integer conic quadratic programming, Oper. Res. Lett., 43, 10-15, (2015) · Zbl 1408.90201
[47] Nemhauser, G; Wolsey, L, A recursive procedure for generating all cuts for 0-1 mixed integer programs, Math. Program., 46, 379-390, (1990) · Zbl 0735.90049
[48] Nemhauser, GL; Savelsbergh, MWP; Sigismondi, GC, MINTO, a mixed integer optimizer, Oper. Res. Lett., 15, 47-58, (1994) · Zbl 0806.90095
[49] Quesada, I; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1992)
[50] Ravemark, DE; Rippin, DWT, Optimal design of a multi-product batch plant, Comput. Chem. Eng., 22, 177-183, (1998)
[51] Sawaya, N.: Reformulations, Relaxations and Cutting Planes for Generalized Disjunctive Programming. Ph.D. thesis, Chemical Engineering Department, Carnegie Mellon University (2006)
[52] Sawaya, N., Laird, C.D., Biegler, L.T., Bonami, P., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Lee, J., Lodi, A., Margot, F., Wächter, A.: CMU-IBM Open Source MINLP Project Test Set. http://egon.cheme.cmu.edu/ibm/page.htm. Accessed 19 April 2016 · Zbl 0880.90105
[53] Stubbs, R; Mehrotra, S, A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 515-532, (1999) · Zbl 0946.90054
[54] Tawarmalani, M; Sahinidis, N, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[55] Türkay, M; Grossmann, IE, Logic-based MINLP algorithms for the optimal synthesis of process networks, Comput. Chem. Eng., 20, 959-978, (1996)
[56] Vecchietti, A., Grossmann, I.E.: LOGMIP: a disjunctive 0-1 non-linear optimizer for process system models. Comput. Chem. Eng. 23(4-5), 555-565 (1999). doi:10.1016/S0098-1354(98)00293-2. http://www.sciencedirect.com/science/article/B6TFT-3XY28Y0-B/2/2709e69a55450cf2263efcc5368850db · Zbl 0946.90054
[57] Vielma, J., Dunning, I., Huchette, J., Lubin, M.: Extended Formulations in Mixed Integer Conic Quadratic Programming. Technical Report. http://arxiv.org/abs/1505.07857 (2015) · Zbl 1387.90165
[58] Zhu, Y; Kuno, T, A disjunctive cutting-plane-based branch-and-cut algorithm for 0-1 mixed-integer convex nonlinear programs, Ind. Eng. Chem. Res., 45, 187-196, (2006)
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.