Convex hull of two quadratic or a conic quadratic and a quadratic inequality. (English) Zbl 1393.90074
This paper contributes to extending the development of strong valid inequalities to mixed integer conic quadratic programming. The analyis is based on results on the convex hull of open sets defined by two strict non-homogenuous quadratic inequalities in the reference [U. Yildiran, IMA J. Math. Control Inf. 26, No. 4, 417–450 (2009; Zbl 1187.90227)]. The authors prove three main results:
- –
- how to extend the aggregation technique of [loc. cit.] to yield valid conic quadratic inequalities for the convex hull of open sets defined by two strict quadratic inequalities or by a strict conic quadratic inequality and a strict quadratic inequality;
- –
- that under an additional containment assumption, these inequalities charcterize the convex hull exactly for sets defined by a strict conic quadratic and a strict quadratic inequality;
- –
- that under certain topological assumptions the results can be transferred to characterize the closed convex hull of sets defined with non-strict conic and quadratic inequalities.
Reviewer: Matthias Ehrgott (Lancaster)
MSC:
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C20 | Quadratic programming |
Software:
SCIPReferences:
| [1] | Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1, 1-41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1 |
| [2] | Andersen, K.; Jensen, A.; Goemans, M. (ed.); Correa, J. (ed.), Intersection cuts for mixed integer conic quadratic sets, No. 7801, 37-48 (2013), Berlin · Zbl 1346.90623 |
| [3] | Atamtürk, A.; Narayanan, V.; Fischetti, M. (ed.); Williamson, DP (ed.), Cuts for conic mixed-integer programming, No. 4513, 16-29 (2007), Berlin · Zbl 1136.90518 |
| [4] | Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122, 1-20 (2010) · Zbl 1184.90112 · doi:10.1007/s10107-008-0239-4 |
| [5] | Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. In: Al-Baali, M., Grandinetti, L., Purnama, A. (eds.) Numerical Analysis and Optimization, Springer Proceedings in Mathematics and Statistics, vol. 134, pp. 1-35. Springer, Switzerland (2015) · Zbl 1330.65083 |
| [6] | Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: On families of quadratic surfaces having fixed intersections with two hyperplanes. Discrete Appl. Math. 161(16), 2778-2793 (2013) · Zbl 1288.90052 · doi:10.1016/j.dam.2013.05.017 |
| [7] | Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: Disjunctive conic cuts for mixed integer second order cone optimization. http://coral.ie.lehigh.edu/ ted/files/papers/ConicCuts14 (2014) · Zbl 1387.90184 |
| [8] | Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72(1), 51-63 (1996) · Zbl 0851.90087 · doi:10.1007/BF02592331 |
| [9] | Bienstock, D., Michalka, A.: Strong formulations for convex functions over nonconvex sets. Optimization online. http://www.optimization-online.org/DB_HTML/2011/12/3278.html (2011) · Zbl 1334.90130 |
| [10] | 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 · doi:10.1137/120878963 |
| [11] | Bixby, R., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-integer programming: a progress report. In: Grötschel, M. (ed.). The Sharpest Cut: The Impact of Manfred Padberg and His Work, chap. 18, pp. 309-326. SIAM, Philadelphia, PA (2004) · Zbl 1152.90542 |
| [12] | Bixby, R., Rothberg, E.: Progress in computational mixed integer programming—a look back from the other side of the tipping point. Ann. Oper. Res. 149, 37-41 (2007) · Zbl 1213.90011 · doi:10.1007/s10479-006-0091-y |
| [13] | Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: Günlük, O., Woeginger, G.J. (eds.). Proceedings of the 15th IPCO Conference, LNCS, vol. 6655, pp. 52-64. Springer, New York (2011) · Zbl 1339.90243 |
| [14] | Burer, S., Kılınç-Karzan, F.: Personal communication (2014) · Zbl 0735.90049 |
| [15] | Burer, S., Kılınç-Karzan, F.: How to convexify the intersection of a second order cone and a nonconvex quadratic. arXiv preprint arXiv:1406.1031. http://arxiv.org/abs/1406.1031 (2014) · Zbl 1358.90095 |
| [16] | Çezik, M.T., Iyengar, G.: Cuts for mixed 0-1 conic programming. Math. Program. 104, 179-202 (2005) · Zbl 1159.90457 · doi:10.1007/s10107-005-0578-3 |
| [17] | Conforti, M., Cornuéjols, G., Zambelli, G.: Polyhedral approaches to mixed integer linear programming. In: 50 Years of Integer Programming 1958-2008, pp. 343-385 (2010) · Zbl 1187.90002 |
| [18] | Conforti, M., Cornuéjols, G., Zambelli, G.: Corner polyhedron and intersection cuts. Surv. Oper. Res. Manag. Sci. 16, 105-120 (2011) · Zbl 1187.90196 |
| [19] | Cook, W.J., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155-174 (1990) · Zbl 0711.90057 · doi:10.1007/BF01580858 |
| [20] | Cornuéjols, G.: Valid inequalities for mixed integer linear programs. Math. Program. 112, 3-44 (2008) · Zbl 1278.90266 · doi:10.1007/s10107-006-0086-0 |
| [21] | Dadush, D., Dey, S.S., Vielma, J.P.: The Chvátal-Gomory closure of a strictly convex body. Math. Oper. Res. 36, 227-239 (2011) · Zbl 1252.90051 · doi:10.1287/moor.1110.0488 |
| [22] | Dadush, D., Dey, S.S., Vielma, J.P.: The split closure of a strictly convex body. Oper. Res. Lett. 39, 121-126 (2011) · Zbl 1225.90085 · doi:10.1016/j.orl.2011.02.002 |
| [23] | Dadush, D., Dey, S.S., Vielma, J.P.: On the Chvátal-Gomory closure of a compact convex set. Math. Program. 145, 327-348 (2014) · Zbl 1298.90056 · doi:10.1007/s10107-013-0649-9 |
| [24] | Del Pia, A., Weismantel, R.: Relaxations of mixed integer sets from lattice-free polyhedra. 4OR: Q. J. Oper. Res. 10, 1-24 (2012) · Zbl 1259.90074 · doi:10.1007/s10288-012-0200-5 |
| [25] | Drewes, S.: Mixed integer second order cone programming. Ph.D. thesis, Technische Universität Darmstadt (2009) · Zbl 1176.90002 |
| [26] | Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2012) · Zbl 0998.49001 |
| [27] | Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 451-558 (1969) · Zbl 0184.23103 · doi:10.1016/0024-3795(69)90017-2 |
| [28] | Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra. Math. Program. 3, 23-85 (1972) · Zbl 0246.90029 · doi:10.1007/BF01584976 |
| [29] | Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P.: Progress in linear programming-based algorithms for integer programming: an exposition. INFORMS J. Comput. 12, 2-23 (2000) · Zbl 1052.90048 · doi:10.1287/ijoc.12.1.2.11900 |
| [30] | Kılınç, M.R., Linderoth, J., Luedtke, J.: Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Optimization online. http://www.optimization-online.org/DB_HTML/2010/11/2808.html (2010) · Zbl 1387.90159 |
| [31] | 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 · doi:10.1287/moor.2015.0737 |
| [32] | Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. Math. Program. 154(1-2), 463-491 (2015) · Zbl 1327.90137 · doi:10.1007/s10107-015-0903-4 |
| [33] | Lodi, A.; Jünger, M. (ed.); Liebling, T. (ed.); Naddef, D. (ed.); Nemhauser, G. (ed.); Pulleyblank, W. (ed.); Reinelt, G. (ed.); Rinaldi, G. (ed.); Wolsey, L. (ed.), Mixed integer programming computation, 619-645 (2010), New York · Zbl 1187.90206 |
| [34] | Marchand, H., Wolsey, L.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363-371 (2001) · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211 |
| [35] | Modaresi, S.: Valid inequalities and reformulation techniques for mixed integer nonlinear programming. Ph.D. thesis, University of Pittsburgh (2015) |
| [36] | Modaresi, S., Kılınç, M.R., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155, 575-611 (2016) · Zbl 1358.90078 · doi:10.1007/s10107-015-0866-5 |
| [37] | Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10-15 (2015) · Zbl 1408.90201 · doi:10.1016/j.orl.2014.10.006 |
| [38] | Modaresi, S., Vielma, J.P.: The power of a negative eigenvalue: aggregation cuts for nonlinear integer programming. In: 2014 Mixed Integer Programming Workshop, July 21-24, 2014, Columbus, OH, Poster. https://mip2014.engineering.osu.edu/sites/mip2014.engineering.osu.edu/files/uploads/Sina-Modaresi (2014) · Zbl 1327.90137 |
| [39] | Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts for conic programming. In: Poster presented at the MIP 2012 Workshop at UC Davis (2012) · Zbl 1408.90201 |
| [40] | Moran, D.A., Dey, S.S., Vielma, J.P.: A strong dual for conic mixed-integer programs. SIAM J. Optim. 22(3), 1136-1150 (2012) · Zbl 1262.90111 · doi:10.1137/110840868 |
| [41] | Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067 · doi:10.1002/9781118627372 |
| [42] | Nemhauser, G.L., Wolsey, L.A.: A recursive procedure to generate all cuts for 0-1 mixed integer programs. Math. Program. 46, 379-390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752 |
| [43] | Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0-1 mixed convex programming. Math. Program. 86, 515-532 (1999) · Zbl 0946.90054 · doi:10.1007/s101070050103 |
| [44] | Wolsey, L.A.: Integer Programming. Wiley, New York (1998) · Zbl 0930.90072 |
| [45] | Yıldıran, U.: Convex hull of two quadratic constraints is an LMI set. IMA J. Math. Control Inf. 26, 417-450 (2009) · Zbl 1187.90227 · doi:10.1093/imamci/dnp023 |
| [46] | Yıldız, S., Cornuéjols, G.: Disjunctive cuts for cross-sections of the second-order cone. Oper. Res. Lett. 43(4), 432-437 (2015) · Zbl 1408.90206 · doi:10.1016/j.orl.2015.06.001 |
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.
