Learning for Spatial Branching: An Algorithm Selection Approach

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Ahmadi AA, Majumdar A (2016) Some applications of polynomial optimization in operations research and real-time decision making. Optim. Lett. 10(4):709–729.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
• Baltean-Lugojan R, Bonami P, Misener R, Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Technical report, Optimization-online 6943.Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Wächter A (2008) Branching and bounds tightening techniques for non-convex MINLP. Technical report, Optimization-online 2059. IBM Research Report RC24620.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 Softw. 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
• Bienstock D, Muñoz G (2018) LP formulations for polynomial optimization problems. SIAM J. Optim. 28(2):1121–1150.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
• Breiman L (2001) Random forests. Machine Learn. 45(1):5–32.Crossref, 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
• Clauset A (2004) Finding community structure in very large networks. Phys. Rev. E. 70(6):066111.Crossref, 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
• 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
• Eggensperger K, Lindauer M, Hutter F (2018) Neural networks for predicting algorithm runtime distributions. Lang J, ed. Proc. 27th Internat. Joint Conf. Artificial Intelligence, 1442–1448.Google Scholar
• Faenza Y, Muñoz G, Pokutta S (2022) New limits of treewidth-based tractability in optimization. Math. Programming 191:559–594.Crossref, Google Scholar
• Fasiolo M, Wood SN, Zaffran M, Nedellec R, Goude Y (2021) Fast calibrated additive quantile regression. J. Amer. Statist. Assoc. 116(535):1402–1412.Crossref, Google Scholar
• Friedman JH (2001) Greedy function approximation: A gradient boosting machine. Ann. Statist. 29(5):1189–1232.Crossref, Google Scholar
• Friedman JH (2002) Stochastic gradient boosting. Comput. Statist. Data Anal. 38(4):367–378.Crossref, Google Scholar
• Fulkerson D, Gross O (1965) Incidence matrices and interval graphs. Pacific J. Math. 15(3):835–855.Crossref, Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2018) QPLIB: A library of quadratic programming instances. Math. Program. Comput. 1:237–265.Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Preprint, submitted, June 4, https://arxiv.org/abs/1906.01629.Google Scholar
• Ghaddar B, Marecek J, Mevissen M (2015) Optimal power flow as a polynomial optimization problem. IEEE Trans. Power Syst. 31(1):539–546.Crossref, Google Scholar
• Ghaddar B, Claeys M, Mevissen M, Eck BJ (2017) Polynomial optimization for water networks: Global solutions for the valve setting problem. Eur. J. Oper. Res. 261(2):450–459.Crossref, Google Scholar
• Gomes CP, Selman B (2001) Algorithm portfolios. Artificial Intelligence 126(1):43–62.Crossref, Google Scholar
• González-Rodríguez B (2022) Advances in polynomial optimization. PhD thesis, University of Santiago de Compostela.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(3):541–568.Crossref, Google Scholar
• Graham DR, Leyton-Brown K, Roughgarden T (2022) Formalizing preferences over runtime distributions. Preprint, submitted May 25, https://arxiv.org/abs/2205.13028.Google Scholar
• Gupta P, Gasse M, Khalil EB, Mudigonda PK, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. 34th Conf. Neural Inform. Processing Systems (NeurIPS 2020), Vancouver, Canada (Neural Information Processing Systems Foundation, Inc. (NeurIPS)).Google Scholar
• Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning, 2nd ed. (Springer, New York).Crossref, Google Scholar
• Hutter F, Xu L, Hoos HH, Leyton-Brown K (2014) Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence 206:79–111.Crossref, 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), 724–731.Google Scholar
• Koenker R (2005) Quantile Regression. Econometric Society Monographs (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Koenker R, Chernozhukov V, He X, Peng L, eds. (2017) Handbook of Quantile Regression (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Kriegler B, Berk R (2010) Small area estimation of the homeless in Los Angeles: An application of cost-sensitive stochastic gradient boosting. Ann. Appl. Statist. 4(3):1234–1255.Crossref, Google Scholar
• Latora V, Nicosia V, Russo G (2017) Complex Networks: Principles, Methods and Applications (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Leyton-Brown K, Nudelman E, Andrew G, McFadden J, Shoham Y (2003) A portfolio approach to algorithm selection. Proc. 18th Internat. Joint Conf. Artificial Intelligence (Morgan Kaufmann Publishers, Inc., San Francisco), 1542–1543.Google Scholar
• Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2):173–187.Link, 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. Mach. Learn. Res. 7:983–999.Google Scholar
• Robertson N, Seymour PD (1984) Graph minors. III. planar tree-width. J. Combin. Theory Ser. B. 36(1):49–64.Crossref, Google Scholar
• Sahinidis NV (2017) BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual.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 (2012a) 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
• Sherali HD, Dalkiran E, Liberti L (2012b) Reduced RLT representations for nonconvex polynomial programming problems. J. Global Optim. 52:447–469.Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99(3):563–591.Crossref, Google Scholar
• Tornede A, Wever M, Werner S, Mohr F, Hüllermeier E (2020) Run2Survive: A decision-theoretic approach to algorithm selection based on survival analysis. Asian Conf. Machine Learning (PMLR), 737–752.Google Scholar
• Wang HJ, Li D (2013) Estimation of extreme conditional quantiles through power transformation. J. Amer. Statist. Assoc. 108(503):1062–1074.Crossref, Google Scholar
• Zarpellon G (2020) Machine learning algorithms in Mixed-Integer Programming. PhD thesis, Université de Montreal.Google Scholar