×

zbMATH — the first resource for mathematics

Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. (English) Zbl 1358.90078
This paper deals with the generalization of split, \(k\)-branch split, and intersection cuts from mixed integer linear programming to the area of mixed integer nonlinear programming. Two techniques are presented that can be used to construct formulas for split, \(k\)-branch split, and general intersection cuts for several classes of convex sets. The authors first introduce an interpolation technique that can be used to construct split and \(k\)-branch split cuts for many classes of sets. Then, the interpolation technique is used to characterize intersection cuts for conic quadratic sets. The authors also introduce an aggregation technique that can be used to construct a wide array of general intersection cuts. The basic principles behind the techniques is presented in a simple, but abstract setting, and then it is utilized to construct more specific cuts to illustrate their power and limitations.

MSC:
90C10 Integer programming
90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
SCIP
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Andersen, K; Cornuéjols, G; Li, Y, Split closure and intersection cuts, Math. Program., 102, 457-493, (2005) · Zbl 1066.90070
[3] Andersen, K., Jensen, A.: Intersection cuts for mixed integer conic quadratic sets. In: Goemans, M., Correa, J. (eds.) 16th International IPCO Conference, Valparaiso, Lecture Notes in Computer Science, pp. 37-48. Springer (2013) · Zbl 1346.90623
[4] Andersen, K; Louveaux, Q; Weismantel, R, An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res., 35, 233-256, (2010) · Zbl 1220.90070
[5] Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol. 166. Springer, Berlin (2012) · Zbl 1235.90002
[6] Atamtürk, A., Narayanan, V.: Cuts for conic mixed-integer programming. In: Fischetti, M., Williamson, D.P. (eds.) IPCO, LNCS, vol. 4513, pp. 16-29. Springer (2007) · Zbl 1136.90518
[7] Atamtürk, A; Narayanan, V, Conic mixed-integer rounding cuts, Math. Program., 122, 1-20, (2010) · Zbl 1184.90112
[8] Balas, E, Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 19-39, (1971) · Zbl 0219.90035
[9] Balas, E; Margot, F, Generalized intersection cuts and a new cut generating paradigm, Math. Program., 137, 19-35, (2013) · Zbl 1262.90099
[10] 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. Optimization Online (2012). http://www.optimization-online.org/DB_HTML/2012/06/3494.html
[11] Belotti, P; Góez, JC; Pólik, I; Ralphs, TK; Terlaky, T, On families of quadratic surfaces having fixed intersections with two hyperplanes, Discrete Appl. Math., 161, 2778-2793, (2013) · Zbl 1288.90052
[12] Bienstock, D., Michalka, A.: Strong formulations for convex functions over nonconvex sets. Optimization Online (2011). http://www.optimization-online.org/DB_HTML/2011/12/3278.html · Zbl 1334.90130
[13] Bienstock, D; Michalka, A, Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24, 643-677, (2014) · Zbl 1334.90130
[14] Billionnet, A; Elloumi, S; Lambert, A, Extending the QCR method to general mixed-integer programs, Math. Program., 131, 381-401, (2012) · Zbl 1235.90100
[15] Billionnet, A; Elloumi, S; Plateau, M, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method, Discrete Appl. Math., 157, 1185-1197, (2009) · Zbl 1169.90405
[16] Bixby, R., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-integer programming: a progress report. In: The Sharpest Cut: The Impact of Manfred Padberg and his Work, chap. 18, pp. 309-326. SIAM, Philadelphia (2004) · Zbl 1152.90542
[17] 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
[18] Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (2013) · Zbl 1260.90006
[19] Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: Gunluk, O., Woeginger, G.J. (eds.): Proceedings of the 15th IPCO Conference, New York, NY, 2011, LNCS, vol. 6655. Springer, pp. 52-64 (2011) · Zbl 1339.90243
[20] Buchheim, C., Caprara, A., Lodi, A.: An effective branch-and-bound algorithm for convex quadratic integer programming. In: Eisenbrand, F., Shepherd, F.B. (eds.): Proceedings of the 14th IPCO Conference, Lausanne, Switzerland, 2010, LNCS, vol. 6080. Springer, pp. 285-298 (2010) · Zbl 1285.90025
[21] Buchheim, C; Caprara, A; Lodi, A, An effective branch-and-bound algorithm for convex quadratic integer programming, Math. Program., 135, 369-395, (2012) · Zbl 1254.90121
[22] Çezik, MT; Iyengar, G, Cuts for mixed 0-1 conic programming, Math. Program., 104, 179-202, (2005) · Zbl 1159.90457
[23] Chvátal, V, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337, (1973) · Zbl 0253.05131
[24] 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
[25] Conforti, M; Cornuéjols, G; Zambelli, G, Corner polyhedron and intersection cuts, Surv. Oper. Res. Manag. Sci., 16, 105-120, (2011) · Zbl 1187.90196
[26] Cook, WJ; Kannan, R; Schrijver, A, Chvátal closures for mixed integer programming problems, Math. Program., 47, 155-174, (1990) · Zbl 0711.90057
[27] Cornuéjols, G, Valid inequalities for mixed integer linear programs, Math. Program., 112, 3-44, (2008) · Zbl 1278.90266
[28] Dadush, D; Dey, SS; Vielma, JP, The chvátal-Gomory closure of a strictly convex body, Math. Oper. Res., 36, 227-239, (2011) · Zbl 1252.90051
[29] Dadush, D., Dey, S.S., Vielma, J.P.: On the Chvátal-Gomory closure of a compact convex set. In: Gunluk, O., Woeginger, G.J. (eds.): Proceedings of the 15th IPCO Conference, New York, NY, 2011, LNCS, vol. 6655. Springer, pp. 130-142 (2011) · Zbl 1339.52006
[30] Dadush, D; Dey, SS; Vielma, JP, The split closure of a strictly convex body, Oper. Res. Lett., 39, 121-126, (2011) · Zbl 1225.90085
[31] Dash, S; Dey, SS; Günlük, O, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra, Math. Program., 135, 221-254, (2012) · Zbl 1269.90068
[32] Dash, S; Günlük, O; Raack, C, A note on the MIR closure and basic relaxations of polyhedra, Oper. Res. Lett., 39, 198-199, (2011) · Zbl 1220.90071
[33] Dash, S; Günlük, O; Vielma, JP, Computational experiments with cross and crooked cross cuts, INFORMS J. Comput., 26, 780-797, (2014) · Zbl 1304.90225
[34] 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
[35] Dey, S.S., Vielma, J.P.: The Chvátal-Gomory closure of an ellipsoid is a polyhedron. In: Eisenbrand, F., Shepherd, F.B. (eds.): Proceedings of the 14th IPCOConference, Lausanne, Switzerland, 2010, LNCS, vol. 6080. Springer, pp. 327-340 (2010) · Zbl 1285.90081
[36] Drewes, S.: Mixed integer second order cone programming. Ph.D. thesis, Technische Universität Darmstadt (2009) · Zbl 1176.90002
[37] Eisenbrand, F., Shepherd, F.B. (eds.): Proceedings of the 14th IPCO Conference, Lausanne, Switzerland, 2010, LNCS, vol. 6080. Springer (2010) · Zbl 1189.90006
[38] Fujie, T; Kojima, M, Semidefinite programming relaxation for nonconvex quadratic programs, J. Glob. Optim., 10, 367-380, (1997) · Zbl 0881.90101
[39] Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: A new approach to the stable set problem based on ellipsoids. In: Gunluk, O., Woeginger, G.J. (eds.): Proceedings of the 15th IPCO Conference, New York, NY, 2011, LNCS, vol. 6655. Springer, pp. 223-234 (2011) · Zbl 1341.90098
[40] Gomory, RE, Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc., 64, 275-278, (1958) · Zbl 0085.35807
[41] Gomory, RE, Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 451-558, (1969) · Zbl 0184.23103
[42] Gomory, RE; Johnson, EL, Some continuous functions related to corner polyhedra, Math. Program., 3, 23-85, (1972) · Zbl 0246.90029
[43] Gouveia, J., Thomas, R.: Convex hulls of algebraic sets. In: Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol. 166. Springer, Berlin, pp. 113-138 (2012) · Zbl 1334.90102
[44] Günlük, O., Woeginger, G.J. (eds.): Proceedings of the 15th IPCO Conference, New York, NY, 2011, LNCS, vol. 6655. Springer (2011)
[45] Helton, J.W., Nie, J.: Semidefinite representation of convex sets and convex hulls. In: Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol. 166. Springer, Berlin, pp. 77-112 (2012) · Zbl 1334.90104
[46] Henrion, D, Semidefinite representation of convex hulls of rational varieties, Acta applicandae mathematicae, 115, 319-327, (2011) · Zbl 1279.90128
[47] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (2003) · Zbl 0704.90057
[48] Johnson, EL; Nemhauser, GL; Savelsbergh, MWP, Progress in linear programming-based algorithms for integer programming: an exposition, INFORMS J. Comput., 12, 2-23, (2000) · Zbl 1052.90048
[49] Kılınç, M.R., Modaresi, S., Vielma, J.P.: Split cuts for conic programming. 9th Mixed Integer Programming Workshop (MIP 2012), July 16-19, 2012, Davis, CA, Poster (2012). https://www.math.ucdavis.edu/static/conferences/mip_2012/posters/poster-sina-modaresi
[50] Kılınç, M.R., Linderoth, J., Luedtke, J.: Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Tech. rep., University of Wisconsin-Madison (2010) · Zbl 0711.90057
[51] Kojima, M; Tunçel, L, Cones of matrices and successive convex relaxations of nonconvex sets, SIAM J. Optim., 10, 750-778, (2000) · Zbl 0966.90062
[52] Lasserre, J, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[53] Li, Y; Richard, JPP, Cook, Kannan and schrijvers example revisited, Discrete Optim., 5, 724-734, (2008) · Zbl 1190.90107
[54] Lodi, A.: Mixed Integer Programming Computation. Springer, New York (2010). chap. 16, pp. 619-645 · Zbl 1187.90206
[55] Lovász, L; Iri, M (ed.); Tanabe, K (ed.), Geometry of numbers and integer programming, 177-210, (1989), Dordrecht
[56] Marchand, H; Wolsey, L, Aggregation and mixed integer rounding to solve mips, Oper. Res., 49, 363-371, (2001) · Zbl 1163.90671
[57] Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer (2002) · Zbl 1140.94010
[58] 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,10-15 (2015) · Zbl 1288.90052
[59] Moran, R; Dey, DA; Vielma, SS, A strong dual for conic mixed-integer programs, SIAM J. Optim., 22, 1136-1150, (2012) · Zbl 1262.90111
[60] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[61] Nemhauser, GL; Wolsey, LA, A recursive procedure to generate all cuts for 0-1 mixed integer programs, Math. Program., 46, 379-390, (1990) · Zbl 0735.90049
[62] Nesterov, Y; Wolkowicz, H; Ye, Y; Saigal, R (ed.); Vandenberghe, L (ed.); Wolkowicz, H (ed.), Nonconvex quadratic optimization, 361-420, (2000), Dordrecht
[63] Oustry, C.: SDP relaxations in combinatorial optimization from a Lagrangian viewpoint. In: Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950), vol. 54, pp. 119-134 (2001) · Zbl 1160.90639
[64] Parrilo, PA, Semidefinite programming relaxations for semialgebraic problems, Math. Program., 96, 293-320, (2003) · Zbl 1043.14018
[65] Pólik, I; Terlaky, T, A survey of the S-lemma, SIAM Rev., 49, 371-418, (2007) · Zbl 1128.90046
[66] Poljak, S; Rendl, F; Wolkowicz, H, A recipe for semidefinite relaxation for (0, 1)-quadratic programming, J. Glob. Optim., 7, 51-73, (1995) · Zbl 0843.90088
[67] Ranestad, K., Sturmfels, B.: The convex hull of a variety. In: Notions of Positivity and the Geometry of Polynomials, pp. 331-344 (2011) · Zbl 1253.14055
[68] Ranestad, K; Sturmfels, B, On the convex hull of a space curve, Adv. Geom., 12, 157-178, (2012) · Zbl 1245.14033
[69] Sanyal, R; Sottile, F; Sturmfels, B, Orbitopes, Mathematika, 57, 275-314, (2011) · Zbl 1315.52001
[70] Scheiderer, C, Convex hulls of curves of genus one, Adv. Math., 228, 2606-2622, (2011) · Zbl 1231.14049
[71] Sherali, H., Adams, W.: A Reformulation-linearization Technique for Solving Discrete and Continuous Nonconvex Problems, vol. 31. Springer, Berlin (1998) · Zbl 0926.90078
[72] Stubbs, RA; Mehrotra, S, A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 515-532, (1999) · Zbl 0946.90054
[73] Tawarmalani, M., Sahinidis, N.: Convexification and Global Optimization in Continuous and Mixed-integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, vol. 65. Springer, Berlin (2002) · Zbl 1031.90022
[74] Vielma, JP, A constructive characterization of the split closure of a mixed integer linear program, Oper. Res. Lett., 35, 29-35, (2007) · Zbl 1278.90277
[75] Wolsey, L.A.: Integer Programming. Wiley, New York (1998) · Zbl 0930.90072
[76] 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
[77] Yıldıran, U; Kose, IE, LMI representations of the convex hulls of quadratic basic semialgebraic sets, J. Convex Anal., 17, 535-551, (2010) · Zbl 1191.14069
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.