×

zbMATH — the first resource for mathematics

Outer-product-free sets for polynomial optimization and oracle-based cuts. (English) Zbl 1450.90024
Summary: This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set \(S \cap P\), where \(S\) is a closed set, and \(P\) is a polyhedron. Given an oracle that provides the distance from a point to \(S\), we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or \(S\)-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of outer-product-free sets, where \(S\) is the set of real, symmetric matrices of the form \(xx^T\). All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach.

MSC:
90C23 Polynomial optimization
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, K.; Jensen, AN; Goemans, M.; Correa, J., Intersection cuts for mixed integer conic quadratic sets, Integer Programming and Combinatorial Optimization, 37-48 (2013), Berlin: Springer, Berlin · Zbl 1346.90623
[2] Andersen, K.; Louveaux, Q.; Weismantel, R., An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res., 35, 1, 233-256 (2010) · Zbl 1220.90070
[3] Andersen, K.; Louveaux, Q.; Weismantel, R.; Wolsey, LA; Fischetti, M.; Williamson, DP, Inequalities from two rows of a simplex tableau, Integer Programming and Combinatorial Optimization, 1-15 (2007), Berlin: Springer, Berlin · Zbl 1136.90517
[4] Anstreicher, KM, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, J. Global Optim., 43, 2-3, 471-484 (2009) · Zbl 1169.90425
[5] Atamtürk, A.; Narayanan, V., Conic mixed-integer rounding cuts, Math. Program., 122, 1, 1-20 (2010) · Zbl 1184.90112
[6] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87, 1, 131-152 (2000) · Zbl 0966.90057
[7] Averkov, G.: On finite generation and infinite convergence of generalized closures from the theory of cutting planes. (2011). arXiv preprint arXiv:1106.1526
[8] Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 1, 19-39 (1971) · Zbl 0219.90035
[9] Balas, E., Disjunctive programming: properties of the convex hull of feasible points, Discret. Appl. Math., 89, 1-3, 3-44 (1998) · Zbl 0921.90118
[10] Balas, E.; Saxena, A., Optimizing over the split closure, Math. Program., 113, 2, 219-240 (2008) · Zbl 1135.90030
[11] Bao, X.; Sahinidis, NV; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs, Optim. Methods Softw., 24, 4-5, 485-504 (2009) · Zbl 1179.90252
[12] Basu, A.; Conforti, M.; Cornuéjols, G.; Zambelli, G., Maximal lattice-free convex sets in linear subspaces, Math. Oper. Res., 35, 3, 704-720 (2010) · Zbl 1218.90130
[13] Basu, A.; Conforti, M.; Cornuéjols, G.; Zambelli, G., Minimal inequalities for an infinite relaxation of integer programs, SIAM J. Discret. Math., 24, 1, 158-168 (2010) · Zbl 1211.90139
[14] Basu, A.; Cornuéjols, G.; Zambelli, G., Convex sets and minimal sublinear functions, J. Convex Anal., 18, 2, 427-432 (2011) · Zbl 1220.26009
[15] Belotti, P.; Góez, JC; Pólik, I.; Ralphs, TK; Terlaky, T., On families of quadratic surfaces having fixed intersections with two hyperplanes, Discret. Appl. Math., 161, 16-17, 2778-2793 (2013) · Zbl 1288.90052
[16] 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
[17] Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252 (1962) · Zbl 0109.38302
[18] Bienstock, D.; Michalka, A., Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24, 2, 643-677 (2014) · Zbl 1334.90130
[19] Bonami, P.; Günlük, O.; Linderoth, J., Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Math. Programm. Comput., 10, 3, 333-382 (2018) · Zbl 1400.90239
[20] Borozan, V.; Cornuéjols, G., Minimal valid inequalities for integer constraints, Math. Oper. Res., 34, 3, 538-546 (2009) · Zbl 1218.90131
[21] Burer, S., Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Programm. Comput., 2, 1, 1-19 (2010) · Zbl 1190.90135
[22] Burer, S.; Vandenbussche, D., Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 181-195 (2009) · Zbl 1170.90522
[23] Chen, J.; Burer, S., Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Programm. Comput., 4, 1, 33-52 (2012) · Zbl 1257.90065
[24] Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discret. Math., 4, 4, 305-337 (1973) · Zbl 0253.05131
[25] Conforti, M.; Cornuéjols, G.; Daniilidis, A.; Lemaréchal, C.; Malick, J., Cut-generating functions and S-free sets, Math. Oper. Res., 40, 2, 276-391 (2014)
[26] Conforti, M.; Cornuéjols, G.; Zambelli, G., Equivalence between intersection cuts and the corner polyhedron, Oper. Res. Lett., 38, 3, 153-155 (2010) · Zbl 1187.90196
[27] Cornuéjols, G.; Wolsey, L.; Yıldız, S., Sufficiency of cut-generating functions, Math. Program., 152, 1-2, 643-651 (2015) · Zbl 1327.90132
[28] Dadush, D.; Dey, SS; Vielma, JP, The split closure of a strictly convex body, Oper. Res. Lett., 39, 2, 121-126 (2011) · Zbl 1225.90085
[29] Dax, A., Low-rank positive approximants of symmetric matrices, Adv. Linear Algebra Matrix Theory, 4, 3, 172-185 (2014)
[30] Del Pia, A.; Weismantel, R., On convergence in mixed integer programming, Math. Program., 135, 1-2, 397-412 (2012) · Zbl 1254.90123
[31] Dey, SS; Wolsey, LA; Lodi, A.; Panconesi, A.; Rinaldi, G., Lifting integer variables in minimal inequalities corresponding to lattice-free triangles, Integer Programming and Combinatorial Optimization, 463-475 (2008), Berlin: Springer, Berlin · Zbl 1143.90359
[32] Dey, SS; Wolsey, LA, Constrained infinite group relaxations of MIPs, SIAM J. Optim., 20, 6, 2890-2912 (2010) · Zbl 1211.90142
[33] Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 3, 211-218 (1936) · JFM 62.1075.02
[34] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Oper. Res., 65, 6, 1615-1637 (2017) · Zbl 1386.90085
[35] Fischetti, M.; Lodi, A., Optimizing over the first Chvátal closure, Math. Program., 110, 1, 3-20 (2007) · Zbl 1192.90125
[36] Fischetti, M.; Salvagnin, D.; Zanette, A., A note on the selection of Benders’ cuts, Math. Program., 124, 1-2, 175-182 (2010) · Zbl 1198.90302
[37] Floudas, CA; Pardalos, PM; Adjiman, C.; Esposito, WR; Gümüs, ZH; Harding, ST; Klepeis, JL; Meyer, CA; Schweiger, CA, Handbook of Test Problems in Local and Global Optimization (2013), Berlin: Springer Science & Business Media, Berlin
[38] Freund, RM; Orlin, JB, On the complexity of four polyhedral set containment problems, Math. Program., 33, 2, 139-145 (1985) · Zbl 0581.90060
[39] Ghaddar, B.; Vera, JC; Anjos, MF, A dynamic inequality generation scheme for polynomial programming, Math. Program., 156, 1-2, 21-57 (2016) · Zbl 1342.90143
[40] Glover, F., Polyhedral convexity cuts and negative edge extensions, Zeitschrift für Oper. Res., 18, 5, 181-186 (1974) · Zbl 0288.90056
[41] Gomory, RE, Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc., 64, 5, 275-278 (1958) · Zbl 0085.35807
[42] Gomory, RE; Graves, RL; Wolfe, P., An algorithm for integer solutions to linear programs, Recent Advances in Mathematical Programming, 269-302 (1963), New York: McGraw-Hill, New York
[43] Gomory, RE; Johnson, EL, Some continuous functions related to corner polyhedra, Math. Program., 3, 1, 23-85 (1972) · Zbl 0246.90029
[44] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 2, 169-197 (1981) · Zbl 0492.90056
[45] Guennebaud, G., Jacob, B., et al.: Eigen v3. (2010). http://eigen.tuxfamily.org
[46] Higham, NJ, Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl., 103, 103-118 (1988) · Zbl 0649.65026
[47] Hillestad, RJ; Jacobsen, SE, Reverse convex programming, Appl. Math. Optim., 6, 1, 63-78 (1980) · Zbl 0448.90044
[48] Hiriart-Urruty, JB; Lemaréchal, C., Fundamentals of Convex Analysis (2012), Berlin: Springer Science & Business Media, Berlin
[49] Kelley, JE Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104
[50] Kılınç-Karzan, F., On minimal valid inequalities for mixed integer conic programs, Math. Oper. Res., 41, 2, 477-510 (2015) · Zbl 1338.90275
[51] Kocuk, B.; Dey, SS; Sun, XA, Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem, Math. Programm. Comput., 10, 4, 557-596 (2018) · Zbl 1411.90249
[52] Konno, H.; Yamamoto, R., Choosing the best set of variables in regression analysis using integer programming, J. Global Optim., 44, 2, 273-282 (2009) · Zbl 1178.62069
[53] Krishnan, K.; Mitchell, JE, A unifying framework for several cutting plane methods for semidefinite programming, Optim. Methods Softw., 21, 1, 57-74 (2006) · Zbl 1181.90215
[54] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[55] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging applications of algebraic geometry, pp 157-270. Springer, Berlin (2009) · Zbl 1163.13021
[56] Li, Y.; Richard, JPP, Cook, Kannan and Schrijver’s example revisited, Discrete Optim., 5, 4, 724-734 (2008) · Zbl 1190.90107
[57] Locatelli, M.; Schoen, F., On convex envelopes for bivariate functions over polytopes, Math. Program., 144, 1-2, 65-91 (2014) · Zbl 1295.90055
[58] Locatelli, M.; Thoai, NV, Finite exact branch-and-bound algorithms for concave minimization over polytopes, J. Global Optim., 18, 2, 107-128 (2000) · Zbl 1001.90069
[59] Lovász, L.: Geometry of numbers and integer programming. Mathematical Programming: Recent Developments and Applications pp. 177-210 (1989)
[60] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 2, 166-190 (1991) · Zbl 0754.90039
[61] Luedtke, J.; Namazifar, M.; Linderoth, J., Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 2, 325-351 (2012) · Zbl 1286.90117
[62] Marchand, H.; Wolsey, LA, Aggregation and mixed integer rounding to solve MIPs, Oper. Res., 49, 3, 363-371 (2001) · Zbl 1163.90671
[63] McCormick, GP, Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems, Math. Program., 10, 1, 147-175 (1976) · Zbl 0349.90100
[64] Meeraus, A.: GLOBALLib. http://www.gamsworld.org/global/globallib.htm
[65] Mirsky, L., Symmetric gauge functions and unitarily invariant norms, Q. J. Math., 11, 1, 50-59 (1960) · Zbl 0105.01101
[66] Misener, R.; Floudas, CA, Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program., 136, 1, 155-182 (2012) · Zbl 1257.90079
[67] Misener, R.; Smadbeck, JB; Floudas, CA, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods and Softw., 30, 1, 215-249 (2015) · Zbl 1325.90071
[68] Modaresi, S.; Kılınç, MR; Vielma, JP, Split cuts and extended formulations for mixed integer conic quadratic programming, Oper. Res. Lett., 43, 1, 10-15 (2015) · Zbl 1408.90201
[69] Modaresi, S.; Kılınç, MR; Vielma, JP, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Math. Program., 155, 1-2, 575-611 (2016) · Zbl 1358.90078
[70] MOSEK ApS: The MOSEK Fusion API for C++ 8.1.0.63 (2018). https://docs.mosek.com/8.1/cxxfusion/index.html
[71] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 1, 60-100 (1991) · Zbl 0734.90060
[72] Porembski, M., Cone adaptation strategies for a finite and exact cutting plane algorithm for concave minimization, J. Global Optim., 24, 1, 89-107 (2002) · Zbl 1026.90072
[73] Qualizza, A., Belotti, P., Margot, F.: Linear programming relaxations of quadratically constrained quadratic programs. In: Mixed Integer Nonlinear Programming pp. 407-426 (2012) · Zbl 1242.90155
[74] Rikun, AD, A convex envelope formula for multilinear functions, J. Global Optim., 10, 4, 425-437 (1997) · Zbl 0881.90099
[75] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton
[76] Saxena, A.; Bonami, P.; Lee, J., Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations, Math. Program., 124, 1-2, 383-411 (2010) · Zbl 1198.90330
[77] Saxena, A.; Bonami, P.; Lee, J., Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Math. Program., 130, 2, 359-413 (2011) · Zbl 1229.90144
[78] Schneider, R., Convex Bodies: The Brunn-Minkowski Theory (2014), Cambridge: Cambridge University Press, Cambridge · Zbl 1287.52001
[79] Schrijver, A., Theory of Linear and Integer Programming (1986), Chichester: Wiley, Chichester · Zbl 0665.90063
[80] Sen, S.; Sherali, HD, Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization, Math. Program., 37, 2, 169-183 (1987) · Zbl 0626.90078
[81] Serrano, F.; Lodi, A.; Nagarajan, V., Intersection cuts for factorable MINLP, Integer Programming and Combinatorial Optimization, 385-398 (2019), Berlin: Springer International Publishing, Berlin · Zbl 1436.90091
[82] Sherali, HD; Fraticelli, BMP, Enhancing RLT relaxations via a new class of semidefinite cuts, J. Global Optim., 22, 1-4, 233-261 (2002) · Zbl 1045.90044
[83] Shor, NZ, Quadratic optimization problems, Sov. J. Comput. Syst. Sci., 25, 1-11 (1987)
[84] Tardella, F., Existence and sum decomposition of vertex polyhedral convex envelopes, Optim. Lett., 2, 3, 363-375 (2008) · Zbl 1152.90614
[85] Tawarmalani, M.; Richard, JPP; Xiong, C., Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138, 1-2, 531-577 (2013) · Zbl 1273.90165
[86] Tawarmalani, M.; Sahinidis, NV, Convex extensions and envelopes of lower semi-continuous functions, Math. Program., 93, 2, 247-263 (2002) · Zbl 1065.90062
[87] Tawarmalani, M.; Sahinidis, NV, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications (2002), Berlin: Springer Science & Business Media, Berlin · Zbl 1031.90022
[88] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249 (2005) · Zbl 1099.90047
[89] Towle, E., Luedtke, J.: Intersection disjunctions for reverse convex sets. (2019). arXiv preprint arXiv:1901.02112 · Zbl 06967051
[90] Tuy, H., Concave programming under linear constraints, Sov. Math., 5, 1437-1440 (1964) · Zbl 0132.40103
[91] Vandenbussche, D.; Nemhauser, G., A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Math. Program., 102, 3, 559-575 (2005) · Zbl 1137.90010
[92] Wolsey, LA; Nemhauser, GL, Integer and Combinatorial Optimization (2014), New York: Wiley, New York
[93] Xia, W., Vera, J.C., Zuluaga, L.F.: Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. (2019)
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.