×

Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization. (English) Zbl 1370.90153

Summary: We introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches in global optimization are based on convex relaxations. Thanks to the fact that only simple bound constraints are present, minimizing the separable underestimator can be done very quickly. The underestimators are computed monomial-wise after the original polynomial has been shifted. We show that such valid underestimators exist and their degree can be bounded when the degree of the polynomial objective function is bounded, too. For the quartic case, all optimal monomial underestimators are determined analytically. We implemented and tested the branch-and-bound algorithm where these underestimators are hardcoded. The comparison against standard global optimization and polynomial optimization solvers clearly shows that our method outperforms the others, the only exception being the binary case where, though, it is still competitive. Moreover, our branch-and-bound approach suffers less in case of dense polynomial objective function, i.e., in case of polynomials having a large number of monomials. This paper is an extended and revised version of the preliminary paper [C. Buchheim and C. D’Ambrosio, Lect. Notes Comput. Sci. 8494, 198–209 (2014; Zbl 1418.90175)].

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Citations:

Zbl 1418.90175

Software:

ANTIGONE; GloptiPoly
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[2] 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
[3] Billionnet, A; Elloumi, S; Lambert, A, Extending the QCR method to general mixed integer programs, Math. Progr., 131, 381-401, (2012) · Zbl 1235.90100
[4] Buchheim, C., D’Ambrosio, C.: Box-constrained mixed-integer polynomial optimization using separable underestimators. In: Integer Programming and Combinatorial Optimization—17th International Conference, IPCO 2014, LNCS, vol. 8494, pp. 198-209 (2014) · Zbl 1418.90175
[5] Buchheim, C; Rinaldi, G, Efficient reduction of polynomial zero-one optimization to the quadratic case, SIAM J. Optim., 18, 1398-1413, (2007) · Zbl 1165.90685
[6] Buchheim, C., Traversi, E.: Separable non-convex underestimators for binary quadratic programming. In: 12th International Symposium on Experimental Algorithms—SEA 2013, LNCS, vol. 7933, pp. 236-247 (2013)
[7] Buchheim, C; Wiegele, A, Semidefinite relaxations for non-convex quadratic mixed-integer programming, Math. Progr., 141, 435-452, (2013) · Zbl 1280.90091
[8] Buchheim, C; Santis, M; Palagi, L; Piacentini, M, An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations, SIAM J. Optim., 23, 1867-1889, (2013) · Zbl 1282.90104
[9] Burer, S, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Progr. Comput., 2, 1-19, (2010) · Zbl 1190.90135
[10] Burer, S; Letchford, AN, Non-convex mixed-integer nonlinear programming: a survey, Surv. Oper. Res. Manag. Sci., 17, 97-106, (2012)
[11] COUENNE (v. 0.4) projects.coin-or.org/Couenne · Zbl 1273.90160
[12] D’Ambrosio, C; Lodi, A, Mixed integer nonlinear programming tools: a practical overview, 4OR, 9, 329-349, (2011) · Zbl 1235.90101
[13] D’Ambrosio, C; Lodi, A, Mixed integer nonlinear programming tools: an updated practical overview, Annals OR, 204, 301-320, (2013) · Zbl 1269.90067
[14] Dua, V, Mixed integer polynomial programming, Comput. Chem. Eng., 72, 387-394, (2015)
[15] Henrion, D; Lasserre, JB; Loefberg, J, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779, (2009) · Zbl 1178.90277
[16] Lasserre, JB, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17, 822-843, (2006) · Zbl 1119.90036
[17] Lasserre, JB; Thanh, TP, Convex underestimators of polynomials, J. Glob Optim., 56, 1-25, (2013) · Zbl 1273.90160
[18] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[19] Parrilo, PA; Sturmfels, B, Minimizing polynomial functions. algorithmic and quantitative real algebraic geometry, DIMACS Ser. Discrete Math. Theor. Comput. Sci., 60, 83-99, (2001)
[20] Rosenberg, IG, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d’Etudes de Recherche Opérationelle, 17, 71-74, (1975) · Zbl 0302.90041
[21] SCIP (v. 3.0.1) http://scip.zib.de/scip.shtml · Zbl 1099.90047
[22] Shor, NZ, Class of global minimum bounds of polynomial functions, Cybernetics, 23, 731-734, (1987) · Zbl 0648.90058
[23] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Progr., 103, 225-249, (2005) · Zbl 1099.90047
[24] Vandenbussche, D; Nemhauser, GL, A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Math. Progr., 102, 559-575, (2005) · Zbl 1137.90010
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.