×

Polyhedral approximation in mixed-integer convex optimization. (English) Zbl 1401.90158

Summary: Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.

MSC:

90C25 Convex programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abhishek, K.; Leyffer, S.; Linderoth, J., FilMINT: an outer approximation-based solver for convex mixed-integer nonlinear programs, INFORMS J. Comput., 22, 555-567, (2010) · Zbl 1243.90142
[2] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[3] Ahmadi, A.; Olshevsky, A.; Parrilo, P.; Tsitsiklis, J., NP-hardness of deciding convexity of quartic polynomials and related problems, Math. Program., 137, 453-476, (2013) · Zbl 1274.90516
[4] Belotti, P., Berthold, T., Neves, K.: Algorithms for discrete nonlinear optimization in FICO Xpress. In: 2016 IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 1-5 (2016)
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172
[6] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics (2001) · Zbl 0986.90032
[7] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[8] Bixby, R., Maes, C., Garcia, R.: Recent developments in the Gurobi optimizer. In: Gurobi Optimization Workshop, INFORMS Annual Meeting, Philadelphia, PA (2015)
[9] Bonami, P.; Biegler, LT; Conn, AR; Cornuéjols, G.; Grossmann, IE; Laird, CD; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discret. Optim., 5, 186-204, (2008) · Zbl 1151.90028
[10] Bonami, P.; KilinÇ, M.; Linderoth, J.; Lee, J. (ed.); Leyffer, S. (ed.), Algorithms and software for convex mixed integer nonlinear programs, No. 154, 1-39, (2012), New York · Zbl 1242.90121
[11] Bonami, Pierre; Lee, Jon; Leyffer, Sven; Wächter, Andreas, On branching rules for convex mixed-integer nonlinear optimization, Journal of Experimental Algorithmics, 18, 2.1-2.31, (2013) · Zbl 1322.90052
[12] Byrd, RH; Nocedal, J.; Waltz, R.; Pillo, G. (ed.); Roma, M. (ed.), KNITRO: an integrated package for nonlinear optimization, 35-59, (2006), Berlin · Zbl 1108.90004
[13] Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049
[14] Diamond, S.; Boyd, S., CVXPY: a python-embedded modeling language for convex optimization, J. Mach. Learn. Res., 17, 1-5, (2016) · Zbl 1360.90008
[15] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[16] Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295-320. doi:10.1137/15M1020575 (2017) · Zbl 1368.90002
[17] Duran, M.; Grossmann, I., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[18] Fourer, R.; Orban, D., DrAmpl: a meta solver for optimization problem analysis, CMS, 7, 437-463, (2009) · Zbl 1243.90005
[19] Gally, T., Pfetsch, M.E., Ulbrich, S.: A framework for solving mixed-integer semidefinite programs. Available on Optimization Online http://www.optimization-online.org/DB_HTML/2016/04/5394.html (2016)
[20] Grant, M.; Boyd, S.; Blondel, V. (ed.); Boyd, S. (ed.); Kimura, H. (ed.), Graph implementations for nonsmooth convex programs, 95-110, (2008), Berlin · Zbl 1205.90223
[21] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)
[22] Grant, M.; Boyd, S.; Ye, Y.; Liberti, L. (ed.); Maculan, N. (ed.), Disciplined convex programming, No. 84, 155-210, (2006), New York · Zbl 1130.90382
[23] Günlük, O.; Linderoth, J.; Lee, J. (ed.); Leyffer, S. (ed.), Perspective reformulation and applications, No. 154, 61-89, (2012), New York · Zbl 1242.90134
[24] Gupta, OK; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 1533-1546, (1985) · Zbl 0591.90065
[25] Harjunkoski, I.; Westerlund, T.; Pörn, 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
[26] Hien, LTK, Differential properties of euclidean projection onto power cone, Math. Methods Oper. Res., 82, 265-284, (2015) · Zbl 1342.90183
[27] 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
[28] Hijazi, H.; Liberti, L., Constraint qualification failure in action, Oper. Res. Lett., 44, 503-506, (2016) · Zbl 1380.90089
[29] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (1996). Two volumes - 2nd printing · Zbl 0795.49001
[30] Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.): 50 Years of Integer Programming 1958-2008—From the Early Years to the State-of-the-Art. Springer, Berlin (2010) · Zbl 1181.90003
[31] Kılınç, M.R.: Disjunctive cutting planes and algorithms for convex mixed integer nonlinear programming. Ph.D. Thesis, University of Wisconsin-Madison (2011)
[32] Leyffer, S.: Deterministic methods for mixed integer nonlinear programming. Ph.D. Thesis, University of Dundee (1993)
[33] Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A., Munson, T., Sharma, M.: Minotaur: toolkit for mixed integer nonlinear optimization problems. https://wiki.mcs.anl.gov/minotaur/index.php/Main_Page. Accessed 16 April 2017
[34] Lobo, Miguel Sousa; Vandenberghe, Lieven; Boyd, Stephen; Lebret, Hervé, Applications of second-order cone programming, Linear Algebra and its Applications, 284, 193-228, (1998) · Zbl 0946.90050
[35] Lubin, Miles; Yamangil, Emre; Bent, Russell; Vielma, Juan Pablo, Extended Formulations in Mixed-Integer Convex Programming, 102-113, (2016), Cham · Zbl 1419.90078
[36] Martin, R.: Large Scale Linear and Integer Optimization: A Unified Approach. Springer, New York (1999) · Zbl 1053.90001
[37] Mittelmann, H.: MINLP benchmark. http://plato.asu.edu/ftp/minlp_old.html. Accessed 13 May 2016
[38] MINLPLIB2 library. http://www.gamsworld.org/minlp/minlplib2/html/. Accessed 13 May 2016
[39] Serrano, S.A.: Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. Ph.D. thesis, Stanford University, Stanford, CA (2015)
[40] Shen, X., Diamond, S., Gu, Y., Boyd, S.: Disciplined Convex-Concave Programming. ArXiv e-prints. http://arxiv.org/abs/1604.02639 (2016)
[41] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[42] Tramontani, A.: Mixed Integer Programming Workshop, June 1st-4th, 2015. The Gleacher Center, Chicago, IL (2015) · Zbl 1230.90042
[43] Udell, M., Mohan, K., Zeng, D., Hong, J., Diamond, S., Boyd, S.: Convex optimization in Julia. In: Proceedings of HPTCDL ’14, pp. 18-28. IEEE Press, Piscataway, NJ, USA (2014)
[44] Vielma, Juan Pablo; Dunning, Iain; Huchette, Joey; Lubin, Miles, Extended formulations in mixed integer conic quadratic programming, Mathematical Programming Computation, 9, 369-418, (2016) · Zbl 1387.90165
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.