×

zbMATH — the first resource for mathematics

On the impact of running intersection inequalities for globally solving polynomial optimization problems. (English) Zbl 1441.90097
Summary: We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations of the form \(z_e = \prod_{v \in e} {z_v}\), \(e \in E\), where \(E\) denotes a set of subsets of cardinality at least two of a ground set. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points \(z\) satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
Reviewer: Reviewer (Berlin)
MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anthony, M.; Boros, E.; Crama, Y.; Gruber, A., Quadratic reformulations of nonlinear binary optimization problems, Math. Program., 162, 1, 115-144 (2017) · Zbl 1358.90074
[2] Bao, X.; Khajavirad, A.; Sahinidis, NV; Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1-37 (2015) · Zbl 1317.90243
[3] Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic \(0-1\) programming, Math. Program., 44, 127-137 (1989) · Zbl 0677.90046
[4] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 479-513 (1983) · Zbl 0624.68087
[5] 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
[6] Berthold, T., Gamrath, G., Hendel, G., Heinz, S., Koch, T., Pfetsch, M., Vigerske, S., Waniek, R., Winkler, M., Wolter, K.: SCIP 3.2, User’s Manual (2016)
[7] Bienstock, D.; Munoz, G., LP furmulations for polynomial optimization problems, SIAM J. Optim., 28, 2, 1121-1150 (2018) · Zbl 1395.80005
[8] Bonami, P.; Günlük, O.; Linderoth, J., Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Math. Program. Comput. (2018) · Zbl 1400.90239
[9] 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
[10] Crama, Y., Concave extensions for non-linear \(0-1\) maximization problems, Math. Program., 61, 53-60 (1993) · Zbl 0796.90040
[11] Crama, Y.; Rodríguez-Heck, E., A class of valid inequalities for multilinear \(0-1\) optimization problems, Discrete Optim., 25, 28-47 (2017) · Zbl 1387.90125
[12] Del Pia, A.; Khajavirad, A., A polyhedral study of binary polynomial programs, Math. Oper. Res., 42, 2, 389-410 (2017) · Zbl 1364.90225
[13] Del Pia, A.; Khajavirad, A., On decomposability of multilinear sets, Math. Program. (2017) · Zbl 1446.90114
[14] Del Pia, A.; Khajavirad, A., The multilinear polytope for acyclic hypergraphs, SIAM J. Optim., 28, 1049-1076 (2018) · Zbl 1396.90048
[15] Del Pia, A., Khajavirad, A.: The running intersection relaxation of the multilinear polytope. Optim. Online manuscript 2018/05/6618 (2018) · Zbl 1396.90048
[16] Dolan, E.; More, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[17] Fix, A., Gruber, A., Boros, E., Zabih, R.: A graph cut algorithm for higher-order Markov random fields. In: 2011 International Conference on Computer Vision, pp. 1020-1027 (2011). 10.1109/ICCV.2011.6126347
[18] GAMS Performance tools. Available at http://www.gams.com/help/topic/gams.doc/solvers/allsolvers.pdf
[19] Helmberg, C.; Rendl, F., Solving quadratic \(0-1\) problems by semidefinite programs and cutting planes, Math. Program., 82, 291-315 (1998) · Zbl 0919.90112
[20] IBM: CPLEX Optimizer (2016). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[21] Karp, R.M.: Reducibility among combinatorial problems. In: Millera, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. New York (1972) · Zbl 1187.90014
[22] Khajavirad, A.; Sahinidis, NV, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput. (2018) · Zbl 1400.90227
[23] Lin, Y.; Schrage, L., The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668 (2009) · Zbl 1177.90325
[24] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I-convex underestimating problems, Math. Program., 10, 147-175 (1976) · Zbl 0349.90100
[25] Meyer, CA; Floudas, CA; Floudas, CA; Pardolos, PM, Trilinear monomials with positive or negative domains: facets of the convex and concave envelopes, Frontiers in Global Optimization, 327-352 (2003), Norwell: Kluwer Academic Publishers, Norwell
[26] Meyer, CA; Floudas, CA, Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes, J. Glob. Optim., 29, 125-155 (2004) · Zbl 1085.90047
[27] Misener, R.; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526 (2014) · Zbl 1301.90063
[28] Padberg, M., The boolean quadric polytope: some characteristics, facets and relatives, Math. Program., 45, 139-172 (1989) · Zbl 0675.90056
[29] POLIP: Library for polynomially constrained mixed-integer programming (2014). http://polip.zib.de
[30] Rikun, AD, A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437 (1997) · Zbl 0881.90099
[31] Ryoo, HS; Sahinidis, NV, Analysis of bounds for multilinear functions, J. Glob. Optim., 19, 403-424 (2001) · Zbl 0982.90054
[32] Sahinidis, N.: Sahinidis optimization group website. http://archimedes.cheme.cmu.edu/?q=baron
[33] Schrijver, A., Theory of Linear and Integer Programming (1986), Chichester: Wiley, Chichester · Zbl 0665.90063
[34] Sherali, HD, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22, 245-270 (1997) · Zbl 0914.90205
[35] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430 (1990) · Zbl 0712.90050
[36] Tarjan, RE; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 3, 566-579 (1984) · Zbl 0545.68062
[37] Tawarmalani, M.: Inclusion certificates and simultaneous convexification of functions. Working paper (2010). http://www.optimization-online.org/DB_FILE/2010/09/2722.pdf
[38] Tawarmalani, M.; Richard, JP; Chung, K., Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124, 481-512 (2010) · Zbl 1198.90298
[39] Tawarmalani, M.; Richard, JP; Xiong, C., Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 531-577 (2013) · Zbl 1273.90165
[40] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591 (2004) · Zbl 1062.90041
[41] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[42] The Optimization Firm, LLC: NLP and MINLP test problems. https://minlp.com/nlp-and-minlp-test-problems
[43] Yajima, Y.; Fujie, T., A polyhedral approach for nonconvex quadratic programming problems with box constraints, J. Glob. Optim., 13, 151-170 (1998) · Zbl 0912.90234
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.