[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Theoretical challenges towards cutting-plane selection

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Packing sets are of the form \(\{x \in \mathbb {R}^n_+ \mid (a^i)^{\top } x \le b_i,\,\forall i \in I \}\) for a possibly infinite set I where all \((a^i,b_i)\)’s are non-negative, i.e., it is not necessarily polyhedral. This generalization is required because while the aggregation closure is a packing set, it is not known if it is polyhedral.

  2. One can show that the integer hull of a packing set is also a packing set [56], and thus so is \(\tilde{P}\).

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

  3. Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007)

  4. Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)

    MathSciNet  MATH  Google Scholar 

  5. Achterberg, T., Raack, C.: The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs. Math. Program. Comput. 2(2), 125–165 (2010)

    MathSciNet  MATH  Google Scholar 

  6. Agra, A., Constantino, M.F.: Lifting two-integer knapsack inequalities. Math. Program. 109, 115–154 (2007)

    MathSciNet  MATH  Google Scholar 

  7. Alvarez, A.M., Louveaux, Q., Wehenkel, L.: A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1), 185–195 (2017)

    MathSciNet  MATH  Google Scholar 

  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(1–2), 87–110 (2014)

    MathSciNet  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  11. Andersen, K., Cornuéjols, G., Li, Y.: Split closure and intersection cuts. Math. Program. 102, 457–493 (2005)

    MathSciNet  MATH  Google Scholar 

  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)

  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(2), 229–238 (2007)

    MathSciNet  MATH  Google Scholar 

  14. Aráoz, J., Evans, L., Gomory, R.E., Johnson, E.L.: Cyclic groups and knapsack facets. Math. Program. 96, 377–408 (2003)

    MathSciNet  MATH  Google Scholar 

  15. Atamtürk, A.: On the facets of the mixed-integer knapsack polyhedron. Math. Program. 98, 145–175 (2003)

    MathSciNet  MATH  Google Scholar 

  16. Atamtürk, A.: Sequence independent lifting for mixed-integer programming. Oper. Res. 52, 487–490 (2004)

    MathSciNet  MATH  Google Scholar 

  17. Atamtürk, A., Günlük, O.: Mingling: mixed-integer rounding with bounds. Math. Program. 123(2), 315–338 (2010)

    MathSciNet  MATH  Google Scholar 

  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(3), 1943–1976 (2017)

    MathSciNet  MATH  Google Scholar 

  19. Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: Conflict graphs in integer programming. Eur. J. Oper. Res. 121, 40–55 (2000)

    MathSciNet  MATH  Google Scholar 

  20. Au, Y.H., Tunçel, L.: A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1), 411–451 (2016)

    MathSciNet  MATH  Google Scholar 

  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)

  22. Averkov, G., Basu, A.: Lifting properties of maximal lattice-free polyhedra. Math. Program. 154(1–2), 81–111 (2015)

    MathSciNet  MATH  Google Scholar 

  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)

  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(2), 459–489 (2015)

    MathSciNet  MATH  Google Scholar 

  25. Balas, E.: Intersection cuts–a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)

    MathSciNet  MATH  Google Scholar 

  26. Balas, E.: Facets of the knapsack polytope. Math. Program. 8, 146–164 (1975)

    MathSciNet  MATH  Google Scholar 

  27. Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3–51 (1979)

    MathSciNet  MATH  Google Scholar 

  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)

  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)

    MATH  Google Scholar 

  30. Balas, E., Ceria, S., Cornuéjols, G., Natraj, N.: Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996)

    MathSciNet  MATH  Google Scholar 

  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(9), 1229–1246 (1996)

    MATH  Google Scholar 

  32. Balas, E., Jeroslow, R.: Strenghtening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)

    MATH  Google Scholar 

  33. Balas, E., Margot, F.: Generalized intersection cuts and a new cut generating paradigm. Math. Program. 137(1), 19–35 (2013)

    MathSciNet  MATH  Google Scholar 

  34. Balas, E., Perregaard, M.: Lift-and-project for mixed 0–1 programming: recent progress. Discrete Appl. Math. 123, 129–154 (2002)

    MathSciNet  MATH  Google Scholar 

  35. Balas, E., Zemel, E.: Facets of knapsack polytope from minimal covers. SIAM J. Appl. Math. 34, 119–148 (1984)

    MathSciNet  MATH  Google Scholar 

  36. Basu, A., Bonami, P., Cornuéjols, G., Margot, F.: Experiments with two-row cuts from degenerate tableaux. INFORMS J. Comput. 23(4), 578–590 (2011)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  39. Basu, A., Conforti, M., Di Summa, M.: A geometric approach to cut-generating functions. Math. Program. 151(1), 153–189 (2015)

    MathSciNet  MATH  Google Scholar 

  40. Basu, A., Conforti, M., Di Summa, M.: Optimal cutting planes from the group relaxations. ArXiv preprint arXiv:1710.07672 (2017)

  41. Basu, A., Cornuéjols, G., Köppe, M.: Unique minimal liftings for simplicial polytopes. Math. Oper. Res. 37(2), 346–355 (2012)

    MathSciNet  MATH  Google Scholar 

  42. Basu, A., Cornuéjols, G., Margot, F.: Intersection cuts with infinite split rank. Math. Oper. Res. 37(1), 21–40 (2012)

    MathSciNet  MATH  Google Scholar 

  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)

  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(1), 105–129 (2014)

    MathSciNet  MATH  Google Scholar 

  45. Basu, A., Hildebrand, R., Köppe, M.: Light on the infinite group relaxation I: foundations and taxonomy. 4OR 14(1), 1–40 (2016)

  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)

  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(2), 1021–1040 (2013)

    MathSciNet  MATH  Google Scholar 

  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)

  49. Basu, A., Paat, J.: Operations that preserve the covering property of the lifting region. SIAM J. Optim. 25(4), 2313–2333 (2015)

    MathSciNet  MATH  Google Scholar 

  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(1), 301–358 (2017)

    MathSciNet  MATH  Google Scholar 

  51. Bell, D.F., Shapiro, J.F.: A convergent duality theory for integer programming. Oper. Res. 25, 419–434 (1977)

    MathSciNet  MATH  Google Scholar 

  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

  53. Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0–1 integer programming. SIAM J. Optim. 15(1), 63–95 (2004)

    MathSciNet  MATH  Google Scholar 

  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(1), 77–91 (2017)

    MathSciNet  MATH  Google Scholar 

  55. Bodur, M., Dash, S., Günlük, O.: Cutting planes from extended LP formulations. Math. Program. 161(1–2), 159–192 (2017)

    MathSciNet  MATH  Google Scholar 

  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

  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)

  58. Bonami, P.: On optimizing over lift-and-project closures. Math. Program. Comput. 4(2), 151–179 (2012)

    MathSciNet  MATH  Google Scholar 

  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

  60. Bonami, P., Margot, F.: Cut generation through binarization. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 174–185. Springer (2014)

  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(4), 288–307 (2005)

    MathSciNet  MATH  Google Scholar 

  62. Borozan, V., Cornuéjols, G.: Minimal valid inequalities for integer constraints. Math. Oper. Res. 34, 538–546 (2009)

    MathSciNet  MATH  Google Scholar 

  63. Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP, Oxford (2013)

    MATH  Google Scholar 

  64. Cadoux, F.: Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Program. 122(2), 197–223 (2010)

    MathSciNet  MATH  Google Scholar 

  65. Caprara, A., Fischetti, M.: \(\{ 0,\frac{1}{2} \}\)–Chvátal-Gomory cuts. Math. Program. 74, 221–235 (1996)

    MATH  Google Scholar 

  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)

  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)

  68. Chandrasekaran, K., Végh, L.A., Vempala, S.S.: The cutting plane method is polynomial for perfect matchings. Math. Oper. Res. 41(1), 23–48 (2016)

    MathSciNet  MATH  Google Scholar 

  69. Chen, B., Küçükyavuz, S., Sen, S.: Finite disjunctive programming characterizations for general mixed-integer linear programs. Oper. Res. 59(1), 202–210 (2011)

    MathSciNet  MATH  Google Scholar 

  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(1), 15–19 (2012)

    MathSciNet  MATH  Google Scholar 

  71. Cheung, K.K.H.: Computation of the lasserre ranks of some polytopes. Math. Oper. Res. 32(1), 88–94 (2007)

    MathSciNet  MATH  Google Scholar 

  72. Chvátal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114(115), 455–499 (1989)

    MathSciNet  MATH  Google Scholar 

  73. Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4), 305–337 (1973)

    MathSciNet  MATH  Google Scholar 

  74. Coleman, T.F.: Large Sparse Numerical Optimization, volume 165 of Lecture Notes in Computer Science, vol. 165. Springer, Berlin (1984)

    Google Scholar 

  75. Conforti, M., Cornuéjols, G., Daniilidis, A., Lemaréchal, C., Malick, J.: Cut-generating functions and s-free sets. Math. Oper. Res. 40(2), 276–391 (2014)

    MathSciNet  MATH  Google Scholar 

  76. Conforti, M., Cornuéjols, G., Zambelli, G.: A geometric perspective on lifting. Oper. Res. 59, 569–577 (2009)

    MathSciNet  MATH  Google Scholar 

  77. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, Berlin (2012)

    MATH  Google Scholar 

  78. Conforti, M., Del Pia, A., Di Summa, M., Faenza, Y.: Reverse split rank. Math. Program. 154(1–2), 273–303 (2015)

    MathSciNet  MATH  Google Scholar 

  79. Conforti, M., Del Pia, A., Di Summa, M., Faenza, Y., Grappe, R.: Reverse Chvátal-Gomory rank. SIAM J. Discrete Math. 29(1), 166–181 (2015)

    MathSciNet  MATH  Google Scholar 

  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)

  81. Coniglio, S., Tieves, M.: On the generation of cutting planes which maximize the bound improvement. In: Bampis, E. (ed.) Experimental Algorithms, pp. 97–109. Springer, Cham (2015)

    Google Scholar 

  82. Cook, W.: Cutting-plane proofs in polynomial space. Math. Program. 47(1–3), 11–18 (1990)

    MathSciNet  MATH  Google Scholar 

  83. Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19–30 (2001)

    MathSciNet  MATH  Google Scholar 

  84. Cook, W., Dash, S., Fukasawa, R., Goycoolea, M.: Numerically safe gomory mixed-integer cuts. INFORMS J. Comput. 21(4), 641–649 (2009)

    MathSciNet  MATH  Google Scholar 

  85. Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 58, 155–174 (1990)

    MATH  Google Scholar 

  86. Cook, W., Koch, T., Steffy, D.E., Wolter, K.: A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Program. Comput. 5(3), 305–344 (2013)

    MathSciNet  MATH  Google Scholar 

  87. Cornuéjols, G.: Revival of the Gomory cuts in the 1990’s. Ann. Oper. Res. 149, 63–66 (2007)

    MathSciNet  MATH  Google Scholar 

  88. Cornuéjols, G., Dawande, M.: A class of hard small 0–1 programs. INFORMS J. Comput. 11, 205–210 (1999)

    MathSciNet  MATH  Google Scholar 

  89. Cornuéjols, G., Lemaréchal, C.: A convex-analysis perspective on disjunctive cuts. Math. Program. 106(3), 567–586 (2006)

    MathSciNet  MATH  Google Scholar 

  90. Cornúejols, G., Li, Y.: Elementary closures for integer programs. Oper. Res. Lett. 28, 1–8 (2001)

    MathSciNet  MATH  Google Scholar 

  91. Cornuéjols, G., Li, Y.: On the rank of mixed 0–1 polyhedra. Math. Program. 91, 391–397 (2002)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  93. Cornuéjols, G., Margot, F., Nannicini, G.: On the safety of gomory cut generators. Math. Program. Comput. 5(4), 345–395 (2013)

    MathSciNet  MATH  Google Scholar 

  94. Cornuéjols, G., Michini, C., Nannicini, G.: How tight is the corner relaxation? Insights gained from the stable set problem. Discrete Optim. 9(2), 109–121 (2012)

    MathSciNet  MATH  Google Scholar 

  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)

  96. Cornuéjols, G., Molinaro, M.: A 3-slope theorem for the infinite relaxation in the plane. Math. Program. 142(1), 83–105 (2013)

    MathSciNet  MATH  Google Scholar 

  97. Crowder, H., Johnson, E.L., Padberg, M.W.: Solving large scale zero-one linear programming problem. Oper. Res. 31, 803–834 (1983)

    MATH  Google Scholar 

  98. Dash, S.: Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Naval Res. Logist. 30, 678–700 (2005)

    MathSciNet  MATH  Google Scholar 

  99. Dash, S., Dey, S.S., Günlük, O.: Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math. Program. 135(1–2), 221–254 (2012)

    MathSciNet  MATH  Google Scholar 

  100. Dash, S., Goycoolea, M.: A heuristic to generate rank-1 GMI cuts. Math. Program. Comput. 2(3–4), 231–257 (2010)

    MathSciNet  MATH  Google Scholar 

  101. Dash, S., Goycoolea, M., Günlük, O.: Two-step MIR inequalities for mixed integer programs. INFORMS J. Comput. 22(2), 236–249 (2010)

    MathSciNet  MATH  Google Scholar 

  102. Dash, S., Günlük, O.: Valid inequalities based on simple mixed-integer sets. Math. Program. 105(1), 29–53 (2006)

    MathSciNet  MATH  Google Scholar 

  103. Dash, S., Günlük, O.: On mixing inequalities: rank, closure, and cutting-plane proofs. SIAM J. Optim. 20(2), 1090–1109 (2009)

    MathSciNet  MATH  Google Scholar 

  104. Dash, S., Günlük, O.: On t-branch split cuts for mixed-integer programs. Math. Program. 141(1–2), 591–599 (2013)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  106. Dash, S., Günlük, O., Vielma, J.P.: Computational experiments with cross and crooked cross cuts. INFORMS J. Comput. 26(4), 780–797 (2014)

    MathSciNet  MATH  Google Scholar 

  107. Dash, S.: Mixed integer rounding cuts and master group polyhedra. Comb. Optim. Methods Appl. 31, 1–32 (2011)

    MATH  Google Scholar 

  108. Dash, S., Dey, S.S., Günlük, O.: On mixed-integer sets with two integer variables. Oper. Res. Lett. 39(5), 305–309 (2011)

    MathSciNet  MATH  Google Scholar 

  109. Del Pia, A., Weismantel, R.: On convergence in mixed integer programming. Math. Program. 135, 397–412 (2012)

    MathSciNet  MATH  Google Scholar 

  110. Del Pia, A.: On the rank of disjunctive cuts. Math. Oper. Res. 37(2), 372–378 (2012)

    MathSciNet  MATH  Google Scholar 

  111. Dey, S.S.: A note on the split rank of intersection cuts. Math. Program. 130(1), 107–124 (2011)

    MathSciNet  MATH  Google Scholar 

  112. Dey, S.S., Iroume, A., Molinaro, M.: Some lower bounds on sparse outer approximations of polytopes. Oper. Res. Lett. 43(3), 323–328 (2015)

    MathSciNet  Google Scholar 

  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)

  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)

  115. Dey, S.S., Louveaux, Q.: Split rank of triangle and quadrilateral inequalities. Math. Oper. Res. 36(3), 432–461 (2011)

    MathSciNet  MATH  Google Scholar 

  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)

  117. Dey, S.S., Molinaro, M., Wang, Q.: Approximating polyhedra with sparse inequalities. Math. Program. 154, 329–352 (2015)

    MathSciNet  MATH  Google Scholar 

  118. Dey, S.S., Richard, J.-P.P.: Facets of the two-dimensional infinite group problems. Math. Oper. Res. 33, 140–166 (2008)

    MathSciNet  MATH  Google Scholar 

  119. Dey, S.S., Richard, J.-P.P.: Relations between facets of low-and high-dimensional group problems. Math. Program. 123(2), 285–313 (2010)

    MathSciNet  MATH  Google Scholar 

  120. Dey, S.S., Richard, J.-P.P., Li, Y., Miller, L.A.: On the extreme inequalities of infinite group problems. Math. Program. 121, 145–170 (2010)

    MathSciNet  MATH  Google Scholar 

  121. Dey, S.S., Wolsey, L.A.: Composite lifting of group inequalities and an application to two-row mixing inequalities. Discrete Optim. 7, 256–268 (2010)

    MathSciNet  MATH  Google Scholar 

  122. Dey, S.S., Wolsey, L.A.: Constrained infinite group relaxations of MIPs. SIAM J. Optim. 20, 2890–2912 (2010)

    MathSciNet  MATH  Google Scholar 

  123. Dey, S.S., Wolsey, L.A.: Two row mixed-integer cuts via lifting. Math. Program. 124(1–2), 143–174 (2010)

    MathSciNet  MATH  Google Scholar 

  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)

  125. Fischetti, M., Lodi, A.: Optimizing over the first Chvátal closure. Math. Program. 110, 3–20 (2007)

    MathSciNet  MATH  Google Scholar 

  126. Fischetti, M., Salvagnin, D.: A relax-and-cut framework for gomory mixed-integer cuts. Math. Program. Comput. 3(2), 79–102 (2011)

    MathSciNet  MATH  Google Scholar 

  127. Fukasawa, R., Goycoolea, M.: On the exact separation of mixed integer knapsack cuts. Math. Program. 128(1–2), 19–41 (2011)

    MathSciNet  MATH  Google Scholar 

  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(4), 913–919 (2006)

    MathSciNet  MATH  Google Scholar 

  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)

  130. Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335–349 (1995)

    MathSciNet  MATH  Google Scholar 

  131. Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)

    MathSciNet  MATH  Google Scholar 

  132. Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, RAND Corporation (1960)

  133. Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 341–375 (1969)

    MathSciNet  MATH  Google Scholar 

  134. Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part I. Math. Program. 3, 23–85 (1972)

    MATH  Google Scholar 

  135. Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part II. Math. Program. 3, 359–389 (1972)

    MATH  Google Scholar 

  136. Gomory, R.E., Johnson, E.L.: T-space and cutting planes. Math. Program. 96, 341–375 (2003)

    MathSciNet  MATH  Google Scholar 

  137. Gomory, R.E., Johnson, E.L., Evans, L.: Corner polyhedra and their connection with cutting planes. Math. Program. 96, 321–339 (2003)

    MathSciNet  MATH  Google Scholar 

  138. Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.P.: Lifted flow cover inequalities for mixed 0–1 integer programs. Math. Program. 85, 439–467 (1999)

    MathSciNet  MATH  Google Scholar 

  139. Guerrero-Garćia, P.: Range-Space Methods for Sparse Linear Programs. Ph.D. thesis, Department of Applied Mathematics, University of Malaga, Spain (2002)

  140. Günlük, O., Pochet, Y.: Mixing mixed-integer inequalities. Math. Program. 90, 429–457 (2001)

    MathSciNet  MATH  Google Scholar 

  141. Guzelsoy, M., Ralphs, T.K.: Duality for mixed-integer linear programs. Int. J. Oper. Res. 4(3), 118–137 (2007)

    MathSciNet  MATH  Google Scholar 

  142. Hammer, P.L., Johnson, E.L., Peled, U.N.: Facet of regular 0–1 polytopes. Math. Program. 8(1), 179–206 (1975)

    MathSciNet  MATH  Google Scholar 

  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)

  144. He, Q., Ahmed, S., Nemhauser, G.L.: A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs. SIAM J. Optim. 21(3), 617–632 (2011)

    MathSciNet  MATH  Google Scholar 

  145. Hoffman, K.L., Padberg, M.: Improving LP-representation of zero-one linear programs for branch-and-cut. ORSA J. Comput. 3, 121–134 (1991)

    MATH  Google Scholar 

  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)

  147. Jeroslow, R.: Cutting-plane theory: algebraic methods. Discrete Math. 23(2), 121–150 (1978)

    MathSciNet  MATH  Google Scholar 

  148. Jeroslow, R.G.: Minimal inequalities. Math. Program. 17(1), 1–15 (1979)

    MathSciNet  MATH  Google Scholar 

  149. Johnson, E.L.: On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)

    MathSciNet  Google Scholar 

  150. Johnson, E.L.: On the group problem and a subadditive approach to integer programming. Ann. Discrete Math. 5, 97–112 (1979)

    MathSciNet  MATH  Google Scholar 

  151. Johnson, E.L.: Characterization of facets for multiple right-hand side choice linear programs. Math. Program. Study 14, 112–142 (1981)

    MATH  Google Scholar 

  152. 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)

    MathSciNet  MATH  Google Scholar 

  153. Johnson, E.L., Padberg, M.W.: Degree-two inequalities, clique facets and biperfect graphs. Ann. Discrete Math. 16, 169–187 (1982)

    MathSciNet  MATH  Google Scholar 

  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, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H.D., Ralphs, T.K., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103–163 (2011)

    MathSciNet  Google Scholar 

  156. Köppe, M., Zhou, Y.: An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem. Oper. Res. Lett. 43(4), 438–444 (2015)

    MathSciNet  Google Scholar 

  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(3), 419–469 (2017)

    MathSciNet  MATH  Google Scholar 

  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)

  159. Kruber, M., Lübbecke, M.E., Parmentier, A.: Learning when to use a decomposition. In: Salvagnin, D., Lombardi, M. (eds.) Integration of AI and OR Techniques in Constraint Programming, pp. 202–210. Springer International Publishing, Cham (2017)

    Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  161. Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)

    MathSciNet  MATH  Google Scholar 

  162. Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3), 470–496 (2003)

    MathSciNet  MATH  Google Scholar 

  163. Lebair, T.M., Basu, A.: Approximation of minimal functions by extreme functions. ArXiv preprint arXiv:1708.04344 (2017)

  164. Letchford, A.N., Lodi, A.: Strengthening Chvátal-Gomory cuts and Gomory fractional cuts. Oper. Res. Lett. 30(2), 74–82 (2002)

    MathSciNet  MATH  Google Scholar 

  165. Li, Y., Richard, J.-P.P.: Cook, Kannan and Schrijver’s example revisited. Discrete Optim. 5, 724–734 (2008)

    MathSciNet  MATH  Google Scholar 

  166. Lodi, A., Pesant, G., Rousseau, L.-M.: On counting lattice points and Chvátal-Gomory cutting planes. In: Achterberg, T., Beck, J.C. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 131–136. Springer, Berlin (2011)

    Google Scholar 

  167. Lodi, A., Zarpellon, G.: On learning and branching: a survey. TOP 25(2), 207–236 (2017)

    MathSciNet  MATH  Google Scholar 

  168. Louveaux, Q., Poirrier, L.: An algorithm for the separation of two-row cuts. Math. Program. 143(1–2), 111–146 (2014)

    MathSciNet  MATH  Google Scholar 

  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)

  170. Lovász, L., Schirjver, A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190 (1991)

    MathSciNet  MATH  Google Scholar 

  171. Marchand, H., Martin, A., Weismantel, R., Wolsey, L.A.: Cutting planes in integer and mixed integer programming. Discrete Appl. Math. 123, 397–446 (2002)

    MathSciNet  MATH  Google Scholar 

  172. Marchand, H., Wolsey, L.A.: The 0–1 knapsack problem with a single continuous variable. Math. Program. 85, 15–33 (1999)

    MathSciNet  MATH  Google Scholar 

  173. Margot, F.: Testing cut generators for mixed-integer linear programming. Math. Program. Comput. 1(1), 69–95 (2009)

    MathSciNet  MATH  Google Scholar 

  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)

  175. Miller, L.A., Li, Y., Richard, J.-P.P.: New inequalities for finite and infinite group problems from approximate lifting. Naval Res. Logist. 55(2), 172–191 (2008)

    MathSciNet  MATH  Google Scholar 

  176. Molinaro, M.: Understanding the Strength of General-Purpose Cutting Planes. Ph.D. thesis, Carnegie Mellon University (2013)

  177. Morán, D.A., Dey, S.S., Vielma, J.P.: A strong dual for conic mixed-integer programs. SIAM J. Optim. 22(3), 1136–1150 (2012)

    MathSciNet  MATH  Google Scholar 

  178. Nannicini, G., Belotti, P., Lee, J., Linderoth, J., Margot, F., Wächter, A.: A probing algorithm for MINLP with failure prediction by SVM. In: Achterberg, T., Beck, J.C. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 154–169. Springer, Berlin (2011)

    Google Scholar 

  179. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)

    MATH  Google Scholar 

  180. 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)

    MathSciNet  MATH  Google Scholar 

  181. Neto, J.: A simple finite cutting plane algorithm for integer programs. Oper. Res. Lett. 40(6), 578–580 (2012)

    MathSciNet  MATH  Google Scholar 

  182. Owen, J.H., Mehrotra, S.: A disjunctive cutting plane procedure for general mixed-integer linear programs. Math. Program. 89(3), 437–448 (2001)

    MathSciNet  MATH  Google Scholar 

  183. Padberg, M.W., Van Roy, T.J., Wolsey, L.A.: Valid linear inequalities for fixed charge problems. Oper. Res. 33, 842–861 (1985)

    MathSciNet  MATH  Google Scholar 

  184. Saunders, M.A., Wright, M.H., Gill, P.E., Murray, W.: Sparse matrix methods in optimization. SIAM J. Sci. Stat. Comput. 5, 562–589 (1984)

    MathSciNet  MATH  Google Scholar 

  185. Pia, A.D., Wagner, C., Weismantel, R.: A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts. Oper. Res. Lett. 39(4), 234–240 (2011)

    MathSciNet  MATH  Google Scholar 

  186. Pokutta, S., Schulz, A.S.: On the rank of cutting-plane proof systems. In: IPCO, pp. 450–463. Springer (2010)

  187. Pokutta, S., Stauffer, G.: Lower bounds for the Chvátal-Gomory rank in the 0/1 cube. Oper. Res. Lett. 39(3), 200–203 (2011)

    MathSciNet  MATH  Google Scholar 

  188. Pudlák, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log. 62(3), 981–998 (1997)

    MathSciNet  MATH  Google Scholar 

  189. Richard, J.-P.P., Dey, S.S.: The Group-theoretic Approach in Mixed Integer Programming, Chapter 19. Springer, Berlin (2010)

    Google Scholar 

  190. Richard, J.-P.P., Li, Y., Miller, L.A.: Valid inequalities for MIPs and group polyhedra from approximate liftings. Math. Program. 118, 253–277 (2009)

    MathSciNet  MATH  Google Scholar 

  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(1), 212–220 (2017)

    MathSciNet  MATH  Google Scholar 

  193. Sanjeevi, S., Kianfar, K.: Mixed n-step MIR inequalities: facets for the n-mixing set. Discrete Optim. 9(4), 216–235 (2012)

    MathSciNet  MATH  Google Scholar 

  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

  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), 1–20 (2005)

    MathSciNet  MATH  Google Scholar 

  196. Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Optim. 3, 411–430 (1990)

    MathSciNet  MATH  Google Scholar 

  197. Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discr. Appl. Math. 52, 83–106 (1994)

    MathSciNet  MATH  Google Scholar 

  198. Sherali, H.D., Smith, J.C., Adams, W.P.: Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations. Discr. Appl. Math. 101, 247–267 (2000)

    MathSciNet  MATH  Google Scholar 

  199. Singh, M., Talwar, K.: Improving integrality gaps via Chvátal–Gomory rounding. In: APPROX-RANDOM, pp. 366–379. Springer (2010)

  200. Van Roy, T.J., Wolsey, L.A.: Valid inequalities for mixed 0–1 programs. Discrete Appl. Math. 14(2), 199–213 (1986)

    MathSciNet  MATH  Google Scholar 

  201. Walter, M.: Sparsity of lift-and-project cutting planes. In: Operations Research Proceedings 2012, pp. 9–14. Springer (2014)

  202. Weismantel, R.: On the 0/1 knapsack polytope. Math. Program. 77(3), 49–68 (1997)

    MathSciNet  MATH  Google Scholar 

  203. Wesselmann, F., Suhl, U.H.: Implementing cutting plane management and selection techniques. Technical report, University of Paderborn, December (2012)

  204. Wolsey, L.A.: Faces for a linear inequality in 0–1 variables. Math. Program. 8, 165–178 (1975)

    MathSciNet  MATH  Google Scholar 

  205. Wolsey, L.A.: Submodularity and valid inequalities in capacitated fixed charge networks. Oper. Res. Lett. 8(3), 119–124 (1989)

    MathSciNet  MATH  Google Scholar 

  206. Wolsey, L.A.: Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  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)

  208. Yildiz, S., Cornuéjols, G.: Cut-generating functions for integer variables. Math. Oper. Res. 41(4), 1381–1403 (2016)

    MathSciNet  MATH  Google Scholar 

  209. Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: Can a pure cutting plane algorithm work? Math. Program. 130(1), 153–176 (2011)

    MathSciNet  MATH  Google Scholar 

  210. Zemel, E.: Lifting the facets of zero-one polytopes. Math. Program. 15, 268–277 (1978)

    MathSciNet  MATH  Google Scholar 

  211. Zhang, M., Küçükyavuz, S.: Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24(4), 1933–1951

Download references

Acknowledgements

We would like to thank Tobias Achterberg, Domenico Salvagnin and Roland Wunderling for their help with preparing this manuscript. We would also like to thank anonymous reviewers for their feedback that greatly improved the presentation of this manuscript. Santanu S. Dey would like to acknowledge the support of NSF CMMI Grant # 1562578. Marco Molinaro would like to acknowledge the support of CNPq grants Universal #431480/2016-8 and Bolsa de Produtividade em Pesquisa #310516/2017-0.

Author information

Authors and Affiliations

  1. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

    Santanu S. Dey

  2. Computer Science Department, PUC-Rio, Rio de Janeiro, Brazil

    Marco Molinaro

Authors
  1. Santanu S. Dey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marco Molinaro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Santanu S. Dey.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dey, S.S., Molinaro, M. Theoretical challenges towards cutting-plane selection. Math. Program. 170, 237–266 (2018). https://doi.org/10.1007/s10107-018-1302-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-018-1302-4

Mathematics Subject Classification

Search

Navigation