Intersection cuts for convex mixed integer programs from translated cones. (English) Zbl 1387.90163
Summary: We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of E. Balas [ Oper. Res. 19, 19–39 (1971; Zbl 0219.90035)]. For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.
Citations:
Zbl 0219.90035References:
| [1] | Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 19-39 (1971) · Zbl 0219.90035 |
| [2] | Balas, E., Integer programming and convex analysis: Intersection cuts from outer polars, Math. Program., 2, 330-382 (1972) · Zbl 0259.90023 |
| [3] | Balas, E.; Margot, F., Generalized intersection cuts and a new cut generating paradigm, Math. Program., 137, 19-35 (2013) · Zbl 1262.90099 |
| [4] | Basu, A.; Cornuéjols, G.; Margot, F., Intersection cuts with infinite split rank, Math. Oper. Res., 37, 21-40 (2012) · Zbl 1242.90117 |
| [5] | Conforti, M.; Cornuéjols, G.; Zambelli, G., Equivalence between intersection cuts and the corner polyhedron, Oper. Res. Lett., 38, 153-155 (2010) · Zbl 1187.90196 |
| [6] | Conforti, M.; Cornuéjols, G.; Zambelli, G., Corner polyhedron and intersection cuts, Surv. Oper. Res. Manag. Sci., 16, 2, 105-120 (2011) · Zbl 1187.90196 |
| [7] | Fischetti, M.; Monaci, M., How tight is the corner relaxation ?, Discrete Optim., 5, 262-269 (2008) · Zbl 1151.90030 |
| [8] | Dey, S. S., A note on the split rank of intersection cuts, Math. Program., 130, 107-124 (2011) · Zbl 1230.90136 |
| [9] | Gomory, R. E., Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 451-558 (1969) · Zbl 0184.23103 |
| [10] | Hiriart-Urruty, J.-B.; Lemaréchal, C., Fundamentals of Convex Analysis (2001), Springer Verlag: Springer Verlag Heidelberg · Zbl 0998.49001 |
| [11] | Çezik, M. T.; Iyengar, G., Cuts for mixed 0-1 conic programmig, Math. Program., 104, 179-202 (2005) · Zbl 1159.90457 |
| [12] | Atamtürk, A.; Narayanan, V., Conic mixed-integer rounding cuts, Math. Program., 122, 1-20 (2010) · Zbl 1184.90112 |
| [13] | Modaresi, S.; Kılınç, M.; Vielma, J. P., Split cuts and extended formulations for mixed integer conic quadratic programming, Oper. Res. Lett., 43, 10-15 (2015) · Zbl 1408.90201 |
| [14] | Dadush, D.; Dey, S.; Vielma, J. P., The split closure of a strictly convex body, Oper. Res. Lett., 39, 121-126 (2011) · Zbl 1225.90085 |
| [15] | Belotti, P.; Goez, J. C.; Polik, 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 (2015), Springer International Publishing), 1-35 · Zbl 1330.65083 |
| [16] | Belotti, P.; Goez, J. C.; Polik, I.; Ralphs, T. K.; Terlaky, T., On families of quadratic surfaces having fixed intersections with two hyperplanes, Discrete Appl. Math., 161, 2778-2793 (2013) · Zbl 1288.90052 |
| [17] | Kılınç-Karzan, F., On minimal valid inequalities for mixed integer conic programs, Math. Oper. Res., 41, 477-510 (2016) · Zbl 1338.90275 |
| [18] | Kılınç-Karzan, F.; Yıldız, S., Two term disjunctions on the second-order cone, Math. Program., 154, 463-491 (2015) · Zbl 1327.90137 |
| [19] | Yıldız, S.; Cornuéjols, G., Disjunctive cuts for cross-sections of the second order cone, Oper. Res. Lett., 43, 432-437 (2015) · Zbl 1408.90206 |
| [20] | Modaresi, S.; Kılınç, M.; Vielma, J. P., Intersection cuts for nonlinear integer programming: Convexification techniques for structured sets, Math. Program., 155, 575-611 (2016) · Zbl 1358.90078 |
| [21] | Andersen, K.; Jensen, A. N., Intersection cuts for mixed integer conic quadratic sets, (Goemans, M.; Correa, J., Proceedings of IPCO 2013 (2013), Springer), 37-48 · Zbl 1346.90623 |
| [22] | Conforti, M.; Cornuéjols, G.; Daniilidis, A.; Lemaréchal, C.; Malick, J., Cut-generating functions and \(S\)-free sets, Math. Oper. Res., 40, 276-301 (2015) · Zbl 1317.52017 |
| [23] | Burer, S.; Kılınç-Karzan, F., How to convexify the intersection of a second order cone and a nonconvex quadratic, Math. Program. (2016) · Zbl 1358.90095 |
| [24] | Bonami, P., Lift-and-project cuts for mixed integer convex programming, (Günlük, O.; Woeginger, G. J., Proceedings of IPCO 2011 (2011), Springer), 52-64 · Zbl 1339.90243 |
| [25] | 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 |
| [26] | Rockafellar, R. T., (Convex Analysis. Convex Analysis, Princeton Mathematical Series (1970), Princeton University Press) · Zbl 0229.90020 |
| [27] | Dey, S.; Morán, D., Some properties of convex hulls of integer points contained in general convex sets, Math. Program., 141, 507-526 (2013) · Zbl 1300.90018 |
| [28] | Basu, A.; Conforti, M.; Cornuéjols, G.; Zambelli, G., Maximal lattice-free convex sets in linear subspaces, Math. Oper. Res., 35, 704-720 (2010) · Zbl 1218.90130 |
| [29] | Moussafir, J.-G., Convex hulls of integral points, J. Math. Sci., 113, 5, 647-665 (2003) · Zbl 1053.52020 |
| [30] | Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order cone, Math. Oper. Res., 26, 193-205 (2001) · Zbl 1082.90133 |
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.
