Non-Monotonicity of Branching Rules with Respect to Linear Relaxations

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universität Berlin, Berlin.Google Scholar
• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Amaldi E, Coniglio S, Gualandi S (2014) Coordinated cutting plane generation via multi-objective separation. Math. Programming 143(1):87–110.Crossref, Google Scholar
• Andreello G, Caprara A, Fischetti M (2007) Embedding {0,1/2}-cuts in a branch-and-cut framework: A computational study. INFORMS J. Comput. 19(2):229–238.Link, Google Scholar
• Applegate D, Bixby R, Chvátal V, Cook W (1995) Finding Cuts in the TSP (A Preliminary Report), vol. 95 (Center for Discrete Mathematics & Theoretical Computer Science, Piscataway, NJ).Google Scholar
• Balas E, Ceria S, Cornuéjols G (1996a) Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Sci. 42(9):1229–1246.Link, Google Scholar
• Balas E, Ceria S, Cornuéjols G, Natraj N (1996b) Gomory cuts revisited. Oper. Res. Lett. 19(1):1–9.Crossref, Google Scholar
• Basu A, Conforti M, Di Summa M, Jiang H (2021) Complexity of branch-and-bound and cutting planes in mixed-integer optimization-II. Internat. Conf. Integer Programming Combinatorial Optim. (Springer, New York), 383–398.Google Scholar
• Basu A, Conforti M, Di Summa M, Jiang H (2023) Complexity of branch-and-bound and cutting planes in mixed-integer optimization. Math. Programming 198(1):787–810.Crossref, Google Scholar
• Basu A, Conforti M, Di Summa M, Zambelli G (2019) Optimal cutting planes from the group relaxations. Math. Oper. Res. 44(4):1208–1220.Link, Google Scholar
• Berthold T, Salvagnin D (2013) Cloud branching. Gomes CP, Sellmann M, eds. Integration of AI and or Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, vol. 7874 (Springer, New York), 28–43.Crossref, Google Scholar
• Bestuzheva K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2021) The SCIP Optimization Suite 8.0. Technical report, Optimization Online. http://www.optimization-online.org/DB_HTML/2021/12/8728.html.Google Scholar
• Bodur M, Dash S, Günlük O (2017) Cutting planes from extended LP formulations. Math. Programming 161(1):159–192.Crossref, Google Scholar
• Cook W (2010) Fifty-plus years of combinatorial integer programming. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art (Springer, Berlin, Heidelberg), 387–430.Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• Dadush D, Tiwari S (2020) On the complexity of branching proofs. Shubhangi S, ed. Proc. 35th Computat. Complexity Conf., Leibniz International Proceedings in Informatics (LIPIcs) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 1–35.Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2(4):393–410.Link, Google Scholar
• Dey SS, Molinaro M (2018) Theoretical challenges towards cutting-plane selection. Math. Programming 170(1):237–266.Crossref, Google Scholar
• Dey SS, Dubey Y, Molinaro M (2021) Branch-and-bound solves random binary IPs in polytime. Proc. 2021 ACM-SIAM Symposium Discrete Algorithms (SODA) (SIAM, Philadelphia), 579–591.Google Scholar
• Dey SS, Dubey Y, Molinaro M, Shah P (2024) A theoretical and computational analysis of full strong-branching. Math. Programming 205(1):303–336.Crossref, Google Scholar
• Gamrath G, Schubert C (2018) Measuring the impact of branching rules for mixed-integer programming. Oper. Res. Proc. 2017: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Freie Universiät Berlin, Germany, September 6–8, 2017 (Springer, New York), 165–170.Google Scholar
• Gläser M, Pfetsch ME (2024) On computing small variable disjunction branch-and-bound trees. Math. Programming 206(1):145–173.Crossref, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2021) MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Math. Programming Comput. 13(3):443–490.Crossref, Google Scholar
• Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64(5):275–278.Crossref, Google Scholar
• Kazachkov AM, Le Bodic P, Sankaranarayanan S (2024) An abstract model for branch and cut. Math. Programming 206(1):175–202.Crossref, Google Scholar
• Land AH, Doig AG (1960) An automatic method of solving discrete programming problems. Econometrica 28(3):497–520.Crossref, Google Scholar
• Le Bodic P, Nemhauser G (2017) An abstract model for branching and its application to mixed integer programming. Math. Programming 166(1–2):369–405.Crossref, Google Scholar
• Linderoth JT, Savelsbergh MW (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2):173–187.Link, Google Scholar
• Lodi A (2010) Mixed integer programming computation. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin, Heidelberg), 619–645.Crossref, Google Scholar
• Lodi A, Tramontani A (2013) Performance variability in mixed-integer programming. Theory Driven by Influential Applications (INFORMS, Catonsville, MD), 1–12.Link, Google Scholar
• Maher S, Miltenberger M, Pedroso JP, Rehfeldt D, Schwarz R, Serrano F (2016) PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. Math. Software – ICMS 2016 (Springer International Publishing, Cham), 301–307.Crossref, Google Scholar
• Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1):60–100.Crossref, Google Scholar
• Shah P, Dey SS, Molinaro M (2025) Non-monotonicity of branching rules with respect to linear relaxations. http://dx.doi.org/10.1287/ijoc.2024.0709.cd, https://github.com/INFORMSJoC/2024.0709.Google Scholar
• Van Roy TJ, Wolsey LA (1987) Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35(1):45–57.Link, Google Scholar
• Wesselmann F, Stuhl U (2012) Implementing cutting plane management and selection techniques. Technical Report (University of Paderborn, Paderborn, Germany).Google Scholar
• Wolsey LA (1975) Faces for a linear inequality in 0–1 variables. Math. Programming 8(1):165–178.Google Scholar