A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization. (English) Zbl 1387.90184
Summary: We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.
Keywords:
second order cone optimization; mixed integer optimization; disjunctive programming; disjunctive conic cutsReferences:
| [1] | Cornuéjols, G., Valid inequalities for mixed integer linear programs, Math. Program., 112, 1, 3-44 (2008) · Zbl 1278.90266 |
| [2] | Balas, E., Disjunctive programming, (Hammer, P. L.; Johnson, E. L.; Korte, B. H., Annals of Discrete Mathematics 5: Discrete Optimization (1979), North Holland), 3-51 · Zbl 0409.90061 |
| [3] | 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-17, 2778-2793 (2013) · Zbl 1288.90052 |
| [4] | 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, (Al-Baali, M.; Grandinetti, L.; Purnama, A., Numerical Analysis and Optimization: NAO-III, Muscat, Oman, January 2014 (2015), Springer International Publishing: Springer International Publishing Cham), 1-35 · Zbl 1330.65083 |
| [5] | Stubbs, R.; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 3, 515-532 (1999) · Zbl 0946.90054 |
| [6] | Çezik, M.; Iyengar, G., Cuts for mixed 0-1 conic programming, Math. Program., 104, 1, 179-202 (2005) · Zbl 1159.90457 |
| [7] | Gomory, R., Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275-278 (1958) · Zbl 0085.35807 |
| [8] | Drewes, S., Mixed integer second order cone programming (2009), Technische Universität Darmstadt: Technische Universität Darmstadt Germany, (Ph.D. thesis) · Zbl 1176.90002 |
| [9] | Andersen, K.; Jensen, A., Intersection cuts for mixed integer conic quadratic sets, (Goemans, M.; Correa, J., Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 7801 (2013), Springer Berlin, Heidelberg), 37-48 · Zbl 1346.90623 |
| [10] | Dadush, D.; Dey, S.; Vielma, J., The split closure of a strictly convex body, Oper. Res. Lett., 39, 2, 121-126 (2011) · Zbl 1225.90085 |
| [11] | Kılınç-Karzan, F.; Yıldız, S., Two-term disjunctions on the second-order cone, (Lee, J.; Vygen, J., Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 8494 (2014), Springer International Publishing), 345-356 · Zbl 1418.90178 |
| [12] | Modaresi, S.; Kılınç, M. R.; Vielma, J. P., Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Math. Program., 155, 1, 575-611 (2016) · Zbl 1358.90078 |
| [13] | 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 |
| [14] | Góez, J. C., Mixed integer second order cone optimization, disjunctive conic cuts: theory and experiments (2013), Lehigh University, (Ph.D. thesis) |
| [15] | Searle, S., (Matrix Algebra Useful for Statistics. Matrix Algebra Useful for Statistics, Wiley Series in Probability and Statistics (1982), Wiley-Interscience) · Zbl 0555.62002 |
| [16] | Golub, G., Some modified matrix eigenvalues problems, SIAM Rev., 15, 2, 318-334 (1973) · Zbl 0254.65027 |
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.
