Learning in Reformulation-Linearization Technique-Based Spatial Branching: Limitations of Strong Branching Imitation

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Balcan M-F, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 344–353.Google Scholar
• Baltean-Lugojan R, Bonami P, Misener R, Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Preprint, November 19, https://optimization-online.org/wp-content/uploads/2018/11/6943.pdf.Google Scholar
• Belotti P, Cafieri S, Lee J, Liberti L (2012) On feasibility based bounds tightening. Accessed July 2025, https://enac.hal.science/hal-00935464.Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Software 24(4–5):597–634.Crossref, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bonami P, Lodi A, Zarpellon G (2022) A classifier to decide on the linearization of mixed-integer quadratic problems in CPLEX. Oper. Res. 70(6):3303–3320.Link, Google Scholar
• Bussieck MR, Drud AS, Meeraus A (2003) MINLPLib—A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15:114–119.Link, Google Scholar
• Dalkiran E, Sherali HD (2013) Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality. J. Global Optim. 57(4):1147–1172.Crossref, Google Scholar
• Dalkiran E, Sherali HD (2016) RLT-POS: Reformulation-linearization technique-based optimization software for solving polynomial programming problems. Math. Programming Comput. 8:337–375.Crossref, Google Scholar
• Dey SS, Dubey Y, Molinaro M, Shah P (2024) A theoretical and computational analysis of full strong-branching. Math. Programming 205:303–336.Crossref, Google Scholar
• Di Liberto G, Kadioglu S, Leo K, Malitsky Y (2016) DASH: Dynamic approach for switching heuristics. Eur. J. Oper. Res. 248(3):943–953.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91:201–213.Crossref, Google Scholar
• Etheve M, Alès Z, Bissuel C, Juan O, Kedad-Sidhoum S (2020) Reinforcement learning for variable selection in a branch and bound algorithm. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer, Cham, Switzerland), 176–185.Google Scholar
• Fan Z, Ghaddar B, Wang X, Xing L, Zhang Y, Zhou Z (2024) Artificial intelligence for operations research: Revolutionizing the operations research process. Preprint, submitted March 26, https://arxiv.org/abs/2401.03244.Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2019) QPLIB: A library of quadratic programming instances. Math. Programming Comput. 11:237–265.Crossref, Google Scholar
• Gamrath G, Schubert C (2018) Measuring the impact of branching rules for mixed-integer programming. Oper. Res. Proc. 2017 Selected Papers Annu. Internat. Conf. German Oper. Res. Soc. GOR (Springer, Cham, Switzerland), 165–170.Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Adv. Neural Inform. Processing Systems 32.Google Scholar
• Ghaddar B, Gómez-Casares I, González-Díaz J, González-Rodríguez B, Pateiro-López B, Rodríguez-Ballesteros S (2023) Learning for spatial branching: An algorithm selection approach. INFORMS J. Comput. 35(5):1024–1043.Link, Google Scholar
• Glankwamdee W (2004) Lookahead branching for mixed integer programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Gomes CP, Selman B (2001) Algorithm portfolios. Artificial Intelligence 126(1):43–62.Crossref, Google Scholar
• Gómez-Casares I, González-Rodríguez B, González-Díaz J, Rodríguez-Fernández P (2024) Impact of domain reduction techniques in polynomial optimization: A computational study. Preprint, submitted March 5, https://arxiv.org/abs/2403.02823.Google Scholar
• González-Rodríguez B, Alvite-Pazó R, Alvite-Pazó S, Ghaddar B, González-Díaz J (2025a) Polynomial optimization: Tightening RLT-based branch-and-bound schemes with conic constraints. J. Optim. Theory Appl. 204(1):12.Crossref, Google Scholar
• González-Rodríguez B, Gómez-Casares I, Ghaddar B, González-Díaz J, Pateiro-López B (2025b) Learning in RLT-based spatial branching: Limitations of strong branching imitation. https://doi.org/10.1287/ijoc.2024.0775.cd, https://github.com/INFORMSJoC/2024.0775.Google Scholar
• González-Rodríguez B, Ossorio-Castillo J, González-Díaz J, González-Rueda ÁM, Penas DR, Rodríguez-Martínez D (2023) Computational advances in polynomial optimization: RAPOSa, a freely available global solver. J. Global Optim. 85:541–568.Crossref, Google Scholar
• Gupta P, Gasse M, Khalil E, Mudigonda P, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Adv. Neural Inform. Processing Systems 33:18087–18097.Google Scholar
• Kannan R, Nagarajan H, Deka D (2024) Strong partitioning and a machine learning approximation for accelerating the global optimization of nonconvex QCQPs. Preprint, submitted September 20, https://arxiv.org/abs/2301.00306v3.Google Scholar
• Khalil EB, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: A survey. TOP 25(2):207–236.Crossref, Google Scholar
• Meinshausen N (2006) Quantile regression forests. J. Machine Learn. Res. 7:983–999.Google Scholar
• Parsonson CWF, Laterre A, Barrett T (2022) Reinforcement learning for branch-and-bound optimisation using retrospective trajectories. Preprint, submitted December 5, https://arxiv.org/abs/2205.14345.Google Scholar
• R Core Team (2021) R: A Language and Environment for Statistical Computing (R Foundation for Statistical Computing, Vienna).Google Scholar
• Scavuzzo L, Aardal K, Lodi A, Yorke-Smith N (2024) Machine learning augmented branch and bound for mixed integer linear programming. Preprint, submitted February 8, https://arxiv.org/abs/2402.05501.Google Scholar
• Scavuzzo L, Chen F, Chételat D, Gasse M, Lodi A, Yorke-Smith N, Aardal K (2022) Learning to branch with tree MDPs. Adv. Neural Inform. Processing Systems 35:18514–18526.Google Scholar
• Sherali HD, Tuncbilek CH (1992) A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2(1):101–112.Crossref, Google Scholar
• Sherali HD, Dalkiran E, Desai J (2012) Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts. Comput. Optim. Appl. 52(2):483–506.Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Programming 99(3):563–591.Crossref, Google Scholar
• Wright MN, Ziegler A (2017) Ranger: A fast implementation of random forests for high dimensional data in C++ and R. J. Statist. Software 77(1):1–17.Crossref, Google Scholar