Theoretical challenges towards cutting-plane selection. (English) Zbl 1391.90427
Summary: While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper, we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection.
MSC:
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Achterberg, T.: Exploiting degeneracy in MIP. In: Talk at Aussois 22nd Combinatorial Optimization Workshop. http://www.iasi.cnr.it/aussois/web/uploads/2018/slides/achterbergt.pdf (2018). Accessed 1 Feb 2018 |
| [2] | Achterberg, T.: LP basis selection and cutting planes. In: Talk at MIP. http://www2.isye.gatech.edu/mip2010/program/program.pdf (2010). Accessed 1 Feb 2018 · Zbl 1408.90326 |
| [3] | Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007) · Zbl 1169.90414 |
| [4] | Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476 |
| [5] | Achterberg, T; Raack, C, The MCF-separator: detecting and exploiting multi-commodity flow structures in mips, Math. Program. Comput., 2, 125-165, (2010) · Zbl 1200.65042 |
| [6] | Agra, A; Constantino, MF, Lifting two-integer knapsack inequalities, Math. Program., 109, 115-154, (2007) · Zbl 1278.90453 |
| [7] | Alvarez, AM; Louveaux, Q; Wehenkel, L, A machine learning-based approximation of strong branching, INFORMS J. Comput., 29, 185-195, (2017) · Zbl 1364.90224 |
| [8] | Alvarez, A.M., Wehenkel, L., Louveaux, Q.: Machine learning to balance the load in parallel branch-and-bound. http://hdl.handle.net/2268/181086 (2015). Accessed 1 Feb 2018 |
| [9] | Amaldi, E; Coniglio, S; Gualandi, S, Coordinated cutting plane generation via multi-objective separation, Math. Program., 143, 87-110, (2014) · Zbl 1286.90094 |
| [10] | Andersen, K; Cornuéjols, G; Li, Y, Reduce-and-split cuts: improving the performance of mixed integer Gomory cuts, Manage. Sci., 51, 1720-1732, (2005) · Zbl 1232.90310 |
| [11] | Andersen, K; Cornuéjols, G; Li, Y, Split closure and intersection cuts, Math. Program., 102, 457-493, (2005) · Zbl 1066.90070 |
| [12] | Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.A.: Inequalities from two rows of a simplex tableau. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings 12th Conference on Integer Programming and Combinatorial Optimization, pp. 30-42. Springer (2007) · Zbl 1136.90517 |
| [13] | Andreello, G; Caprara, A; Fischetti, M, Embedding \(\{0, 1/2\}\)-cuts in a branch-and-cut framework: a computational study, INFORMS J. Comput., 19, 229-238, (2007) · Zbl 1241.90181 |
| [14] | Aráoz, J; Evans, L; Gomory, RE; Johnson, EL, Cyclic groups and knapsack facets, Math. Program., 96, 377-408, (2003) · Zbl 1082.90094 |
| [15] | Atamtürk, A, On the facets of the mixed-integer knapsack polyhedron, Math. Program., 98, 145-175, (2003) · Zbl 1082.90073 |
| [16] | Atamtürk, A, Sequence independent lifting for mixed-integer programming, Oper. Res., 52, 487-490, (2004) · Zbl 1165.90576 |
| [17] | Atamtürk, A; Günlük, O, Mingling: mixed-integer rounding with bounds, Math. Program., 123, 315-338, (2010) · Zbl 1190.90104 |
| [18] | Atamtürk, A; Küçükyavuz, S; Tezel, B, Path cover and path pack inequalities for the capacitated fixed-charge network flow problem, SIAM J. Optim., 27, 1943-1976, (2017) · Zbl 1370.90151 |
| [19] | Atamtürk, A; Nemhauser, GL; Savelsbergh, MWP, Conflict graphs in integer programming, Eur. J. Oper. Res., 121, 40-55, (2000) · Zbl 0959.90034 |
| [20] | Au, YH; Tunçel, L, A comprehensive analysis of polyhedral lift-and-project methods, SIAM J. Discrete Math., 30, 411-451, (2016) · Zbl 1332.90219 |
| [21] | Au, Y.H., Tunçel, L.: Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators. ArXiv preprint arXiv:1608.07647 (2016) · Zbl 0946.90056 |
| [22] | Averkov, G; Basu, A, Lifting properties of maximal lattice-free polyhedra, Math. Program., 154, 81-111, (2015) · Zbl 1328.90084 |
| [23] | Averkov, G., Basu, A., Paat, J.: Approximation of corner polyhedra with families of intersection cuts. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 51-62. Springer (2017) · Zbl 1418.90171 |
| [24] | Awate, Y; Cornuéjols, G; Guenin, B; Tunçel, L, On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs, Math. Program., 150, 459-489, (2015) · Zbl 1309.90061 |
| [25] | Balas, E, Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 19-39, (1971) · Zbl 0219.90035 |
| [26] | Balas, E, Facets of the knapsack polytope, Math. Program., 8, 146-164, (1975) · Zbl 0316.90046 |
| [27] | Balas, E, Disjunctive programming, Ann. Discrete Math., 5, 3-51, (1979) · Zbl 0409.90061 |
| [28] | Balas, E., Bonami, P.: New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 89-103. Springer (2007) · Zbl 1136.90399 |
| [29] | Balas, E; Ceria, S; Cornuéjols, G, A lift-and-project cutting plane algorithm for mixed integer 0-1 programs, Math. Program., 58, 295-324, (1993) · Zbl 0796.90041 |
| [30] | Balas, E; Ceria, S; Cornuéjols, G; Natraj, N, Gomory cuts revisited, Oper. Res. Lett., 19, 1-9, (1996) · Zbl 0865.90098 |
| [31] | Balas, E; Ceria, S; Cornuéjols, G, Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Manage. Sci., 42, 1229-1246, (1996) · Zbl 0880.90105 |
| [32] | Balas, E; Jeroslow, R, Strenghtening cuts for mixed integer programs, Eur. J. Oper. Res., 4, 224-234, (1980) · Zbl 0439.90064 |
| [33] | Balas, E; Margot, F, Generalized intersection cuts and a new cut generating paradigm, Math. Program., 137, 19-35, (2013) · Zbl 1262.90099 |
| [34] | Balas, E; Perregaard, M, Lift-and-project for mixed 0-1 programming: recent progress, Discrete Appl. Math., 123, 129-154, (2002) · Zbl 1076.90031 |
| [35] | Balas, E; Zemel, E, Facets of knapsack polytope from minimal covers, SIAM J. Appl. Math., 34, 119-148, (1984) · Zbl 0385.90083 |
| [36] | Basu, A; Bonami, P; Cornuéjols, G; Margot, F, Experiments with two-row cuts from degenerate tableaux, INFORMS J. Comput., 23, 578-590, (2011) · Zbl 1243.90143 |
| [37] | Basu, A; Bonami, P; Cornuéjols, G; Margot, F, On the relative strength of split, triangle and qudrilateral cuts, Math. Program., 126, 281-314, (2011) · Zbl 1206.90103 |
| [38] | 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 |
| [39] | Basu, A; Conforti, M; Summa, M, A geometric approach to cut-generating functions, Math. Program., 151, 153-189, (2015) · Zbl 1328.90085 |
| [40] | Basu, A., Conforti, M., Di Summa, M.: Optimal cutting planes from the group relaxations. ArXiv preprint arXiv:1710.07672 (2017) · Zbl 1302.90160 |
| [41] | Basu, A; Cornuéjols, G; Köppe, M, Unique minimal liftings for simplicial polytopes, Math. Oper. Res., 37, 346-355, (2012) · Zbl 1242.90116 |
| [42] | Basu, A; Cornuéjols, G; Margot, F, Intersection cuts with infinite split rank, Math. Oper. Res., 37, 21-40, (2012) · Zbl 1242.90117 |
| [43] | Basu, A., Cornuéjols, G., Molinaro, M.: A probabilistic analysis of the strength of the split and triangle closures. In: IPCO, pp. 27-38. Springer (2011) · Zbl 1298.90055 |
| [44] | Basu, A; Hildebrand, R; Köppe, M, Equivariant perturbation in Gomory and johnson’s infinite group problem. I. the one-dimensional case, Math. Oper. Res., 40, 105-129, (2014) · Zbl 1308.90106 |
| [45] | Basu, A., Hildebrand, R., Köppe, M.: Light on the infinite group relaxation I: foundations and taxonomy. 4OR 14(1), 1-40 (2016) · Zbl 1353.90089 |
| [46] | Basu, A., Hildebrand, R., Köppe, M.: Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms. 4OR 14(2), 107-131 (2016) · Zbl 0956.90021 |
| [47] | Basu, A; Hildebrand, R; Koppe, M; Molinaro, M, A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation, SIAM J. Optim., 23, 1021-1040, (2013) · Zbl 1300.90017 |
| [48] | Basu, A., Hildebrand, R., Molinaro, M.: Minimal cut-generating functions are nearly extreme. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 202-213. Springer (2016) · Zbl 1419.90117 |
| [49] | Basu, A; Paat, J, Operations that preserve the covering property of the lifting region, SIAM J. Optim., 25, 2313-2333, (2015) · Zbl 1327.90125 |
| [50] | Basu, A; Hildebrand, R; Köppe, M, Equivariant perturbation in Gomory and johnson’s infinite group problem-III: foundations for the \(k\)-dimensional case with applications to \(k=2\), Math. Program., 163, 301-358, (2017) · Zbl 1380.90190 |
| [51] | Bell, DF; Shapiro, JF, A convergent duality theory for integer programming, Oper. Res., 25, 419-434, (1977) · Zbl 0381.90079 |
| [52] | Benchetrit, Y., Fiorini, S., Huynh, T., Weltge, S.: Characterizing polytopes in the 0/1-cube with bounded chvátal-gomory rank. Math. Oper. Res. (2018). https://doi.org/10.1287/moor.2017.0880 · Zbl 1190.90107 |
| [53] | Bienstock, D; Zuckerberg, M, Subset algebra lift operators for 0-1 integer programming, SIAM J. Optim., 15, 63-95, (2004) · Zbl 1077.90041 |
| [54] | Bodur, M; Dash, S; Günlük, O; Luedtke, J, Strengthened benders cuts for stochastic integer programs with continuous recourse, INFORMS J. Comput., 29, 77-91, (2017) · Zbl 1364.90220 |
| [55] | Bodur, M; Dash, S; Günlük, O, Cutting planes from extended LP formulations, Math. Program., 161, 159-192, (2017) · Zbl 1356.90089 |
| [56] | Bodur, M., Del Pia, A., Dey, S.S., Molinaro, M., Pokutta, S.: Aggregation-based cutting-planes for packing and covering integer programs. Math. Program. (2017). https://doi.org/10.1007/s10107-017-1192-x · Zbl 1010.90061 |
| [57] | Bodur, M., Del Pia, A., Dey, S.S., Molinaro, M.: Lower bounds on the lattice-free rank for packing and covering integer programs. ArXiv preprint arXiv:1710.00031 (2017) · Zbl 1359.90088 |
| [58] | Bonami, P, On optimizing over lift-and-project closures, Math. Program. Comput., 4, 151-179, (2012) · Zbl 1275.90042 |
| [59] | Bonami, P., Lodi, A., Zarpellon, G.: Learning a classification of mixed-integer quadratic programming problems. http://cerc-datascience.polymtl.ca/wp-content/uploads/2018/01/Technical-Report_DS4DM-2017-013.pdf (2017). Accessed 1 Feb 2018 · Zbl 1511.90304 |
| [60] | Bonami, P., Margot, F.: Cut generation through binarization. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 174-185. Springer (2014) · Zbl 1418.90174 |
| [61] | Bonami, P; Minoux, M, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Discrete Optim., 2, 288-307, (2005) · Zbl 1172.90450 |
| [62] | Borozan, V; Cornuéjols, G, Minimal valid inequalities for integer constraints, Math. Oper. Res., 34, 538-546, (2009) · Zbl 1218.90131 |
| [63] | Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP, Oxford (2013) · Zbl 1279.60005 |
| [64] | Cadoux, F, Computing deep facet-defining disjunctive cuts for mixed-integer programming, Math. Program., 122, 197-223, (2010) · Zbl 1184.90105 |
| [65] | Caprara, A; Fischetti, M, \(\{ 0,\frac{1}{2} \}\)-chvátal-Gomory cuts, Math. Program., 74, 221-235, (1996) · Zbl 0855.90088 |
| [66] | Carøe, C.C.: Decomposition in Stochastic Integer Programming. Ph.D. thesis, Institute of Mathematical Sciences, Department of Operations Research, University of Copenhagen, Denmark (1998) · Zbl 0920.90107 |
| [67] | Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA, pp. 106-115 (2000) · Zbl 0970.90069 |
| [68] | Chandrasekaran, K; Végh, LA; Vempala, SS, The cutting plane method is polynomial for perfect matchings, Math. Oper. Res., 41, 23-48, (2016) · Zbl 1334.90077 |
| [69] | Chen, B; Küçükyavuz, S; Sen, S, Finite disjunctive programming characterizations for general mixed-integer linear programs, Oper. Res., 59, 202-210, (2011) · Zbl 1218.90132 |
| [70] | Chen, B; Küçükyavuz, S; Sen, S, A computational study of the cutting plane tree algorithm for general mixed-integer linear programs, Oper. Res. Lett., 40, 15-19, (2012) · Zbl 1242.90123 |
| [71] | Cheung, KKH, Computation of the Lasserre ranks of some polytopes, Math. Oper. Res., 32, 88-94, (2007) · Zbl 1278.90331 |
| [72] | Chvátal, V; Cook, W; Hartmann, M, On cutting-plane proofs in combinatorial optimization, Linear Algebra Appl., 114, 455-499, (1989) · Zbl 0676.90059 |
| [73] | Chvátal, V, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337, (1973) · Zbl 0253.05131 |
| [74] | Coleman, T.F.: Large Sparse Numerical Optimization, volume 165 of Lecture Notes in Computer Science, vol. 165. Springer, Berlin (1984) · Zbl 0536.65047 |
| [75] | Conforti, M; Cornuéjols, G; Daniilidis, A; Lemaréchal, C; Malick, J, Cut-generating functions and s-free sets, Math. Oper. Res., 40, 276-391, (2014) · Zbl 1317.52017 |
| [76] | Conforti, M; Cornuéjols, G; Zambelli, G, A geometric perspective on lifting, Oper. Res., 59, 569-577, (2009) · Zbl 1257.90053 |
| [77] | Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, Berlin (2012) · Zbl 1307.90001 |
| [78] | Conforti, M; Pia, A; Summa, M; Faenza, Y, Reverse split rank, Math. Program., 154, 273-303, (2015) · Zbl 1327.90117 |
| [79] | Conforti, M; Pia, A; Summa, M; Faenza, Y; Grappe, R, Reverse chvátal-Gomory rank, SIAM J. Discrete Math., 29, 166-181, (2015) · Zbl 1335.90059 |
| [80] | Conforti, M., Wolsey, L.A.: “Facet” Separation with One Linear Program. Technical report, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) (2016) · Zbl 1082.90144 |
| [81] | Coniglio, S; Tieves, M; Bampis, E (ed.), On the generation of cutting planes which maximize the bound improvement, 97-109, (2015), Cham |
| [82] | Cook, W, Cutting-plane proofs in polynomial space, Math. Program., 47, 11-18, (1990) · Zbl 0735.90048 |
| [83] | Cook, W; Dash, S, On the matrix-cut rank of polyhedra, Math. Oper. Res., 26, 19-30, (2001) · Zbl 1073.90574 |
| [84] | Cook, W; Dash, S; Fukasawa, R; Goycoolea, M, Numerically safe Gomory mixed-integer cuts, INFORMS J. Comput., 21, 641-649, (2009) · Zbl 1243.90135 |
| [85] | Cook, W; Kannan, R; Schrijver, A, Chvátal closures for mixed integer programming problems, Math. Program., 58, 155-174, (1990) · Zbl 0711.90057 |
| [86] | Cook, W; Koch, T; Steffy, DE; Wolter, K, A hybrid branch-and-bound approach for exact rational mixed-integer programming, Math. Program. Comput., 5, 305-344, (2013) · Zbl 1305.90310 |
| [87] | Cornuéjols, G, Revival of the Gomory cuts in the 1990’s, Ann. Oper. Res., 149, 63-66, (2007) · Zbl 1213.90015 |
| [88] | Cornuéjols, G; Dawande, M, A class of hard small 0-1 programs, INFORMS J. Comput., 11, 205-210, (1999) · Zbl 1040.90534 |
| [89] | Cornuéjols, G; Lemaréchal, C, A convex-analysis perspective on disjunctive cuts, Math. Program., 106, 567-586, (2006) · Zbl 1149.90175 |
| [90] | Cornúejols, G; Li, Y, Elementary closures for integer programs, Oper. Res. Lett., 28, 1-8, (2001) · Zbl 1108.90326 |
| [91] | Cornuéjols, G; Li, Y, On the rank of mixed 0-1 polyhedra, Math. Program., 91, 391-397, (2002) · Zbl 1049.90040 |
| [92] | Cornuéjols, G; Li, Y; Vandenbussche, D, K-cuts: a variation of Gomory mixed integer cuts from the LP tableau, INFORMS J. Comput., 15, 385-396, (2003) · Zbl 1238.90105 |
| [93] | Cornuéjols, G; Margot, F; Nannicini, G, On the safety of Gomory cut generators, Math. Program. Comput., 5, 345-395, (2013) · Zbl 1305.90311 |
| [94] | Cornuéjols, G; Michini, C; Nannicini, G, How tight is the corner relaxation? insights gained from the stable set problem, Discrete Optim., 9, 109-121, (2012) · Zbl 1252.90052 |
| [95] | Cornuéjols, G., Lee, D.L.: On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 300-311. Springer (2016) · Zbl 1242.90128 |
| [96] | Cornuéjols, G; Molinaro, M, A 3-slope theorem for the infinite relaxation in the plane, Math. Program., 142, 83-105, (2013) · Zbl 1282.90106 |
| [97] | Crowder, H; Johnson, EL; Padberg, MW, Solving large scale zero-one linear programming problem, Oper. Res., 31, 803-834, (1983) · Zbl 0576.90065 |
| [98] | Dash, S, Exponential lower bounds on the lengths of some classes of branch-and-cut proofs, Naval Res. Logist., 30, 678-700, (2005) · Zbl 1082.90143 |
| [99] | 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 |
| [100] | Dash, S; Goycoolea, M, A heuristic to generate rank-1 GMI cuts, Math. Program. Comput., 2, 231-257, (2010) · Zbl 1208.90120 |
| [101] | Dash, S; Goycoolea, M; Günlük, O, Two-step MIR inequalities for mixed integer programs, INFORMS J. Comput., 22, 236-249, (2010) · Zbl 1243.90146 |
| [102] | Dash, S; Günlük, O, Valid inequalities based on simple mixed-integer sets, Math. Program., 105, 29-53, (2006) · Zbl 1085.90034 |
| [103] | Dash, S; Günlük, O, On mixing inequalities: rank, closure, and cutting-plane proofs, SIAM J. Optim., 20, 1090-1109, (2009) · Zbl 1198.90300 |
| [104] | Dash, S; Günlük, O, On t-branch split cuts for mixed-integer programs, Math. Program., 141, 591-599, (2013) · Zbl 1280.90089 |
| [105] | Dash, S; Günlük, O; Molinaro, M, On the relative strength of different generalizations of split cuts, Discrete Optim., 16, 36-50, (2015) · Zbl 1387.90155 |
| [106] | 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 |
| [107] | Dash, S, Mixed integer rounding cuts and master group polyhedra, Comb. Optim. Methods Appl., 31, 1-32, (2011) · Zbl 1326.90053 |
| [108] | Dash, S; Dey, SS; Günlük, O, On mixed-integer sets with two integer variables, Oper. Res. Lett., 39, 305-309, (2011) · Zbl 1252.90053 |
| [109] | Pia, A; Weismantel, R, On convergence in mixed integer programming, Math. Program., 135, 397-412, (2012) · Zbl 1254.90123 |
| [110] | Pia, A, On the rank of disjunctive cuts, Math. Oper. Res., 37, 372-378, (2012) · Zbl 1242.90125 |
| [111] | Dey, SS, A note on the split rank of intersection cuts, Math. Program., 130, 107-124, (2011) · Zbl 1230.90136 |
| [112] | Dey, SS; Iroume, A; Molinaro, M, Some lower bounds on sparse outer approximations of polytopes, Oper. Res. Lett., 43, 323-328, (2015) · Zbl 1408.90326 |
| [113] | Dey, S.S., Iroume, A., Wang, G.: The strength of multi-row aggregation cuts for sign-pattern integer programs. ArXiv preprint arXiv:1711.06963 (2017) · Zbl 1085.90034 |
| [114] | Dey, S.S., Lodi, A., Wolsey, L.A., Tramontani, A.: Experiments with two row tableau cuts. In: Eisenbrand, F., Shepherd, B. (eds.) Proceedings 14th Conference on Integer Programming and Combinatorial Optimization, pp. 424-437. Springer (2010) · Zbl 1285.90047 |
| [115] | Dey, SS; Louveaux, Q, Split rank of triangle and quadrilateral inequalities, Math. Oper. Res., 36, 432-461, (2011) · Zbl 1242.90127 |
| [116] | Dey, S.S., Molinaro, M., Wang, Q.: Analysis of sparse cutting planes for sparse MILPs with applications to stochastic MILPs. Math. Oper. Res 43(1), 304-332 (2018) · Zbl 1269.90068 |
| [117] | Dey, SS; Molinaro, M; Wang, Q, Approximating polyhedra with sparse inequalities, Math. Program., 154, 329-352, (2015) · Zbl 1327.90134 |
| [118] | Dey, SS; Richard, J-PP, Facets of the two-dimensional infinite group problems, Math. Oper. Res., 33, 140-166, (2008) · Zbl 1190.90105 |
| [119] | Dey, SS; Richard, J-PP, Relations between facets of low-and high-dimensional group problems, Math. Program., 123, 285-313, (2010) · Zbl 1194.90062 |
| [120] | Dey, SS; Richard, J-PP; Li, Y; Miller, LA, On the extreme inequalities of infinite group problems, Math. Program., 121, 145-170, (2010) · Zbl 1184.90113 |
| [121] | Dey, SS; Wolsey, LA, Composite lifting of group inequalities and an application to two-row mixing inequalities, Discrete Optim., 7, 256-268, (2010) · Zbl 1242.90128 |
| [122] | Dey, SS; Wolsey, LA, Constrained infinite group relaxations of mips, SIAM J. Optim., 20, 2890-2912, (2010) · Zbl 1211.90142 |
| [123] | Dey, SS; Wolsey, LA, Two row mixed-integer cuts via lifting, Math. Program., 124, 143-174, (2010) · Zbl 1247.90205 |
| [124] | Espinoza, D.: Computing with multiple-row Gomory cuts. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Proceedings 13th Conference on Integer Programming and Combinatorial Optimization, pp. 214-224. Springer (2008) · Zbl 1143.90363 |
| [125] | Fischetti, M; Lodi, A, Optimizing over the first chvátal closure, Math. Program., 110, 3-20, (2007) · Zbl 1192.90125 |
| [126] | Fischetti, M; Salvagnin, D, A relax-and-cut framework for Gomory mixed-integer cuts, Math. Program. Comput., 3, 79-102, (2011) · Zbl 1257.90057 |
| [127] | Fukasawa, R; Goycoolea, M, On the exact separation of mixed integer knapsack cuts, Math. Program., 128, 19-41, (2011) · Zbl 1218.90126 |
| [128] | Gentile, C; Ventura, P; Weismantel, R, Mod-2 cuts generation yields the convex hull of bounded integer feasible sets, SIAM J. Discrete Math., 20, 913-919, (2006) · Zbl 1136.90023 |
| [129] | Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The SCIP optimization suite 5.0. Technical Report 17-61, ZIB, Takustr.7, 14195 Berlin (2017) · Zbl 0711.90057 |
| [130] | Goemans, MX, Worst-case comparison of valid inequalities for the TSP, Math. Program., 69, 335-349, (1995) · Zbl 0844.90101 |
| [131] | Gomory, RE, Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc., 64, 275-278, (1958) · Zbl 0085.35807 |
| [132] | Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, RAND Corporation (1960) · Zbl 0735.90048 |
| [133] | Gomory, RE, Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 341-375, (1969) · Zbl 0184.23103 |
| [134] | Gomory, RE; Johnson, EL, Some continuous functions related to corner polyhedra, part I, Math. Program., 3, 23-85, (1972) · Zbl 0246.90029 |
| [135] | Gomory, RE; Johnson, EL, Some continuous functions related to corner polyhedra, part II, Math. Program., 3, 359-389, (1972) · Zbl 0254.90036 |
| [136] | Gomory, RE; Johnson, EL, T-space and cutting planes, Math. Program., 96, 341-375, (2003) · Zbl 1082.90144 |
| [137] | Gomory, RE; Johnson, EL; Evans, L, Corner polyhedra and their connection with cutting planes, Math. Program., 96, 321-339, (2003) · Zbl 1082.90145 |
| [138] | Gu, Z; Nemhauser, GL; Savelsbergh, MWP, Lifted flow cover inequalities for mixed 0-1 integer programs, Math. Program., 85, 439-467, (1999) · Zbl 0977.90030 |
| [139] | Guerrero-Garćia, P.: Range-Space Methods for Sparse Linear Programs. Ph.D. thesis, Department of Applied Mathematics, University of Malaga, Spain (2002) · Zbl 1257.90053 |
| [140] | Günlük, O; Pochet, Y, Mixing mixed-integer inequalities, Math. Program., 90, 429-457, (2001) · Zbl 1041.90033 |
| [141] | Guzelsoy, M; Ralphs, TK, Duality for mixed-integer linear programs, Int. J. Oper. Res., 4, 118-137, (2007) · Zbl 1160.90600 |
| [142] | Hammer, PL; Johnson, EL; Peled, UN, Facet of regular 0-1 polytopes, Math. Program., 8, 179-206, (1975) · Zbl 0314.90064 |
| [143] | He, H., Daumé III, H., Eisner, J.: Learning to search in branch-and-bound algorithms. In: Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS’14, pp. 3293-3301. MIT Press, Cambridge, MA, USA (2014) · Zbl 1278.90331 |
| [144] | He, Q; Ahmed, S; Nemhauser, GL, A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs, SIAM J. Optim., 21, 617-632, (2011) · Zbl 1230.90138 |
| [145] | Hoffman, KL; Padberg, M, Improving LP-representation of zero-one linear programs for branch-and-cut, ORSA J. Comput., 3, 121-134, (1991) · Zbl 0755.90062 |
| [146] | Hutter, F., Hoos, H. H., Leyton-Brown, K.: Automated configuration of mixed integer programming solvers. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, 2010. Proceedings, pp. 186-202 (2010) · Zbl 1334.90077 |
| [147] | Jeroslow, R, Cutting-plane theory: algebraic methods, Discrete Math., 23, 121-150, (1978) · Zbl 0406.90055 |
| [148] | Jeroslow, RG, Minimal inequalities, Math. Program., 17, 1-15, (1979) · Zbl 0437.90063 |
| [149] | Johnson, EL, On the group problem for mixed integer programming, Math. Program. Study, 2, 137-179, (1974) · Zbl 0356.90038 |
| [150] | Johnson, EL, On the group problem and a subadditive approach to integer programming, Ann. Discrete Math., 5, 97-112, (1979) · Zbl 0409.90060 |
| [151] | Johnson, EL, Characterization of facets for multiple right-hand side choice linear programs, Math. Program. Study, 14, 112-142, (1981) · Zbl 0449.90070 |
| [152] | 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 |
| [153] | Johnson, EL; Padberg, MW, Degree-two inequalities, clique facets and biperfect graphs, Ann. Discrete Math., 16, 169-187, (1982) · Zbl 0523.52009 |
| [154] | Khalil, E.B., Bodic, P.L., Song, L., Nemhauser, G.L., Dilkina, B.: Learning to branch in mixed integer programming. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, pp. 724-731. AAAI Press (2016) |
| [155] | Koch, T; Achterberg, T; Andersen, E; Bastert, O; Berthold, T; Bixby, RE; Danna, E; Gamrath, G; Gleixner, AM; Heinz, S; Lodi, A; Mittelmann, HD; Ralphs, TK; Salvagnin, D; Steffy, DE; Wolter, K, Miplib 2010, Math. Program. Comput., 3, 103-163, (2011) |
| [156] | Köppe, M; Zhou, Y, An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem, Oper. Res. Lett., 43, 438-444, (2015) · Zbl 1408.90002 |
| [157] | Köppe, M; Zhou, Y, New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem, Math. Program. Comput., 9, 419-469, (2017) · Zbl 1387.90138 |
| [158] | Köppe, M., Zhou, Y.: On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 330-342. Springer (2017) · Zbl 1419.90095 |
| [159] | Kruber, M; Lübbecke, ME; Parmentier, A; Salvagnin, D (ed.); Lombardi, M (ed.), Learning when to use a decomposition, 202-210, (2017), Cham · Zbl 1489.68253 |
| [160] | Kurpisz, A; Leppänen, S; Mastrolilli, M, On the hardest problem formulations for the 0/1 Lasserre hierarchy, Math. Oper. Res., 42, 135-143, (2017) · Zbl 1359.90088 |
| [161] | Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061 |
| [162] | Laurent, M, A comparison of the Sherali-Adams, lovász-schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 470-496, (2003) · Zbl 1082.90084 |
| [163] | Lebair, T.M., Basu, A.: Approximation of minimal functions by extreme functions. ArXiv preprint arXiv:1708.04344 (2017) · Zbl 1380.90190 |
| [164] | Letchford, AN; Lodi, A, Strengthening chvátal-Gomory cuts and Gomory fractional cuts, Oper. Res. Lett., 30, 74-82, (2002) · Zbl 1027.90062 |
| [165] | Li, Y; Richard, J-PP, Cook, Kannan and schrijver’s example revisited, Discrete Optim., 5, 724-734, (2008) · Zbl 1190.90107 |
| [166] | Lodi, A; Pesant, G; Rousseau, L-M; Achterberg, T (ed.); Beck, JC (ed.), On counting lattice points and chvátal-Gomory cutting planes, 131-136, (2011), Berlin · Zbl 1302.90257 |
| [167] | Lodi, A; Zarpellon, G, On learning and branching: a survey, TOP, 25, 207-236, (2017) · Zbl 1372.90003 |
| [168] | Louveaux, Q; Poirrier, L, An algorithm for the separation of two-row cuts, Math. Program., 143, 111-146, (2014) · Zbl 1285.90019 |
| [169] | Lovász, L.: Geometry of numbers and integer programming. In: Iri, M., Tanabe, K. (eds.) Mathematical Programming: Recent Developments and Applications, pp. 177-210. Kluwer, Dordrecht (1989) · Zbl 0683.90054 |
| [170] | Lovász, L; Schirjver, A, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190, (1991) · Zbl 0754.90039 |
| [171] | Marchand, H; Martin, A; Weismantel, R; Wolsey, LA, Cutting planes in integer and mixed integer programming, Discrete Appl. Math., 123, 397-446, (2002) · Zbl 1130.90370 |
| [172] | Marchand, H; Wolsey, LA, The 0-1 knapsack problem with a single continuous variable, Math. Program., 85, 15-33, (1999) · Zbl 0956.90021 |
| [173] | Margot, F, Testing cut generators for mixed-integer linear programming, Math. Program. Comput., 1, 69-95, (2009) · Zbl 1171.90478 |
| [174] | Mastrolilli, M.: High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts. In: Eisenbrand, F., Könemann, J. (eds) Integer Programming and Combinatorial Optimization—19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, volume 10328 of Lecture Notes in Computer Science, pp. 405-416. Springer (2017) · Zbl 1418.90167 |
| [175] | Miller, LA; Li, Y; Richard, J-PP, New inequalities for finite and infinite group problems from approximate lifting, Naval Res. Logist., 55, 172-191, (2008) · Zbl 1152.90664 |
| [176] | Molinaro, M.: Understanding the Strength of General-Purpose Cutting Planes. Ph.D. thesis, Carnegie Mellon University (2013) · Zbl 1243.90143 |
| [177] | Morán, DA; Dey, SS; Vielma, JP, A strong dual for conic mixed-integer programs, SIAM J. Optim., 22, 1136-1150, (2012) · Zbl 1262.90111 |
| [178] | Nannicini, G; Belotti, P; Lee, J; Linderoth, J; Margot, F; Wächter, A; Achterberg, T (ed.); Beck, JC (ed.), A probing algorithm for MINLP with failure prediction by SVM, 154-169, (2011), Berlin · Zbl 1302.90160 |
| [179] | Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067 |
| [180] | 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 |
| [181] | Neto, J, A simple finite cutting plane algorithm for integer programs, Oper. Res. Lett., 40, 578-580, (2012) · Zbl 1258.90052 |
| [182] | Owen, JH; Mehrotra, S, A disjunctive cutting plane procedure for general mixed-integer linear programs, Math. Program., 89, 437-448, (2001) · Zbl 1017.90066 |
| [183] | Padberg, MW; Roy, TJ; Wolsey, LA, Valid linear inequalities for fixed charge problems, Oper. Res., 33, 842-861, (1985) · Zbl 0579.90072 |
| [184] | Saunders, MA; Wright, MH; Gill, PE; Murray, W, Sparse matrix methods in optimization, SIAM J. Sci. Stat. Comput., 5, 562-589, (1984) · Zbl 0559.65042 |
| [185] | Pia, AD; Wagner, C; Weismantel, R, A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts, Oper. Res. Lett., 39, 234-240, (2011) · Zbl 1242.90126 |
| [186] | Pokutta, S., Schulz, A.S.: On the rank of cutting-plane proof systems. In: IPCO, pp. 450-463. Springer (2010) · Zbl 1284.03260 |
| [187] | Pokutta, S; Stauffer, G, Lower bounds for the chvátal-Gomory rank in the 0/1 cube, Oper. Res. Lett., 39, 200-203, (2011) · Zbl 1219.90106 |
| [188] | Pudlák, P, Lower bounds for resolution and cutting plane proofs and monotone computations, J. Symb. Log., 62, 981-998, (1997) · Zbl 0945.03086 |
| [189] | Richard, J.-P.P., Dey, S.S.: The Group-theoretic Approach in Mixed Integer Programming, Chapter 19. Springer, Berlin (2010) |
| [190] | Richard, J-PP; Li, Y; Miller, LA, Valid inequalities for MIPs and group polyhedra from approximate liftings, Math. Program., 118, 253-277, (2009) · Zbl 1171.90006 |
| [191] | Rothvoß, T.: The Lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP. Tutorial. https://sites.math.washington.edu/ rothvoss/lecturenotes/lasserresurvey.pdf (2013). Accessed 1 Feb 2018 |
| [192] | Rothvoß, T; Sanità, L, 0/1 polytopes with quadratic chvátal rank, Oper. Res., 65, 212-220, (2017) · Zbl 1364.90223 |
| [193] | Sanjeevi, S; Kianfar, K, Mixed n-step MIR inequalities: facets for the n-mixing set, Discrete Optim., 9, 216-235, (2012) · Zbl 1281.90030 |
| [194] | Schrijver, A.: On cutting planes. Ann. Discrete Math. 9, 291-296 (1980). Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part II · Zbl 0441.90070 |
| [195] | Sen, S; Higle, J, The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: set convexification, Math. Program., 104, 1-20, (2005) · Zbl 1159.90464 |
| [196] | Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Optim., 3, 411-430, (1990) · Zbl 0712.90050 |
| [197] | Sherali, HD; Adams, WP, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discr. Appl. Math., 52, 83-106, (1994) · Zbl 0819.90064 |
| [198] | Sherali, HD; Smith, JC; Adams, WP, Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations, Discr. Appl. Math., 101, 247-267, (2000) · Zbl 0946.90056 |
| [199] | Singh, M., Talwar, K.: Improving integrality gaps via Chvátal-Gomory rounding. In: APPROX-RANDOM, pp. 366-379. Springer (2010) · Zbl 1306.90138 |
| [200] | Roy, TJ; Wolsey, LA, Valid inequalities for mixed 0-1 programs, Discrete Appl. Math., 14, 199-213, (1986) · Zbl 0593.90058 |
| [201] | Walter, M.: Sparsity of lift-and-project cutting planes. In: Operations Research Proceedings 2012, pp. 9-14. Springer (2014) · Zbl 1305.90313 |
| [202] | Weismantel, R, On the 0/1 knapsack polytope, Math. Program., 77, 49-68, (1997) · Zbl 0891.90130 |
| [203] | Wesselmann, F., Suhl, U.H.: Implementing cutting plane management and selection techniques. Technical report, University of Paderborn, December (2012) · Zbl 1286.90094 |
| [204] | Wolsey, LA, Faces for a linear inequality in 0-1 variables, Math. Program., 8, 165-178, (1975) · Zbl 0314.90063 |
| [205] | Wolsey, LA, Submodularity and valid inequalities in capacitated fixed charge networks, Oper. Res. Lett., 8, 119-124, (1989) · Zbl 0674.90027 |
| [206] | Wolsey, L.A.: Integer Programming. Wiley, New York (1998) · Zbl 0930.90072 |
| [207] | Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Hydra-MIP: automated algorithm configuration and selection for mixed-integer programming. In: RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence (IJCAI) (2011) · Zbl 1200.65042 |
| [208] | Yildiz, S; Cornuéjols, G, Cut-generating functions for integer variables, Math. Oper. Res., 41, 1381-1403, (2016) · Zbl 1349.90638 |
| [209] | Zanette, A; Fischetti, M; Balas, E, Lexicography and degeneracy: can a pure cutting plane algorithm work?, Math. Program., 130, 153-176, (2011) · Zbl 1229.90101 |
| [210] | Zemel, E, Lifting the facets of zero-one polytopes, Math. Program., 15, 268-277, (1978) · Zbl 0428.90042 |
| [211] | Zhang, M., Küçükyavuz, S.: Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24(4), 1933-1951 · Zbl 1311.90081 |
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.
