Estimating the Size of Branch-and-Bound Trees

References

• Achterberg T, Wunderling R (2013) Mixed integer programming: Analyzing 12 years of progress. Jünger M, Reinelt G, eds. Facets of Combinatorial Optimization (Springer, Berlin), 449–481.Crossref, Google Scholar
• Achterberg T, Koch T, Martin A (2006) MIPLIB 2003. Oper. Res. Lett. 34(4):1–12.Crossref, Google Scholar
• Ahmadizadeh K, Dilkina B, Gomes CP, Sabharwal A (2010) An empirical study of optimization for maximizing diffusion in networks. Cohen D, ed. Principles and Practice of Constraint Programming (Springer, Berlin), 514–521.Google Scholar
• Alvarez AM, Louveaux Q, Wehenkel L (2016) Online learning for strong branching approximation in branch-and-bound. Technical report, Université de Liège, Liège, Belgium.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
• Anderson D, Hendel G, Le Bodic P, Viernickel JM (2019) Clairvoyant restarts in branch-and-bound search using online tree-size estimation. Proc. 33rd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1427–1434.Google Scholar
• Balcan MF, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learning, Stockholm, 353–362.Google Scholar
• Belov G, Esler S, Fernando D, Le Bodic P, Nemhauser GL (2017) Estimating the size of search trees by sampling with domain knowledge. Proc. 26th Internat. Joint Conf. Artificial Intelligence, Melbourne, Australia, 473–479.Google Scholar
• Bixby RE, Ceria S, McZeal CM, Savelsbergh MW (1998) An updated mixed integer programming library: MIPLIB 3.0. Optima 58:12–15.Google Scholar
• Breiman L (2001) Random forests. Machine Learning 45(1):5–32.Crossref, Google Scholar
• Breiman L, Friedman JH, Olshen RA, Stone CJ (1983) Classification and Regression Trees (Chapman & Hall/CRC, Boca Raton, FL).Google Scholar
• Chen PC (1992) Heuristic sampling: A method for predicting the performance of tree searching programs. SIAM J. Comput. 21(2):295–315.Crossref, Google Scholar
• Coral (2016) Coral MIP benchmark library. Accessed August 24, 2021, http://coral.ise.lehigh.edu/data-sets/mixed-integer-instances.Google Scholar
• Cornuéjols G, Karamanov M, Li Y (2006) Early estimates of the size of branch-and-bound trees. INFORMS J. Comput. 18(1):86–96.Link, Google Scholar
• Dakin RJ (1965) A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3):250–255.Crossref, Google Scholar
• Fischetti M, Lodi A, Zarpellon G (2019) Learning MILP resolution outcomes before reaching time-limit. Rousseau LM, Stergiou K, eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer, Cham, Switzerland), 275–291.Crossref, Google Scholar
• Friedman JH (2001) Greedy function approximation: A gradient boosting machine. Ann. Statist. 29(5):1189–1232.Crossref, Google Scholar
• Gamrath G, Anderson D, Bestuzheva K, Chen WK, Eifler L, Gasse M, Gemander P, et al. (2020) The SCIP optimization suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin, http://nbn-resolving.de/urn:nbn:de:0297-zib-78023.Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, New York).Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel PM, et al. (2019) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Preprint, submitted July 12, http://www.optimization-online.org/DB_HTML/2019/07/7285.html.Google Scholar
• Håstad J (1999) Clique is hard to approximate within n1−ε. Acta Math. 182(1):105–142.Crossref, Google Scholar
• Hendel G (2018) Adaptive large neighborhood search for mixed integer programming. ZIB-Report 18-60, Zuse Institute Berlin, https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7116.Google Scholar
• Holt CC (2004) Forecasting seasonals and trends by exponentially weighted moving averages. Internat. J. Forecasting 20(1):5–10.Crossref, Google Scholar
• Hyndman R, Koehler A, Ord J, Snyder R (2008) Forecasting with Exponential Smoothing: The State Space Approach (Springer, Berlin).Crossref, Google Scholar
• Iwata Y, Oka K, Yoshida Y (2014) Linear-time FPT algorithms via network flow. Chekuri C, ed. Proc. 2014 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1749–1761.Google Scholar
• Khalil EB, Dilkina B, Nemhauser G, Ahmed S, Shao Y (2017) Learning to run heuristics in tree search. Proc. 26th Internat. Joint Conf. Artificial Intelligence, Melbourne, Australia, 659–666.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
• Kilby P, Slaney JK, Thiébaux S, Walsh T (2006) Estimating search tree size. Proc. 21st National Conf. Artificial Intelligence, vol. 2 (AAAI Press, Palo Alto, CA), 1014–1019.Google Scholar
• Knuth DE (1975) Estimating the efficiency of backtrack programs. Math. Comp. 29(129):121–136.Crossref, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, Gamrath G, Gleixner AM, Heinz S, Lodi A, et al. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.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 GL (2015) How important are branching decisions: Fooling MIP solvers. Oper. Res. Lett. 43(3):273–278.Crossref, Google Scholar
• Lelis LHS, Otten L, Dechter R (2013) Predicting the size of depth-first branch and bound search trees. Proc. 23rd Internat. Joint Conf. Artificial Intelligence, Beijing, (AAAI Press, Palo Alto, CA), 594–600.Google Scholar
• Lodi A (2010) Mixed integer programming computation. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008—From the Early Years to the State-of-the-Art (Springer, Berlin), 619–645.Crossref, Google Scholar
• Nemhauser GL, Trotter LE (1974) Properties of vertex packing and independence system polyhedra. Math. Programming 6(1):48–61.Crossref, Google Scholar
• Nemhauser GL, Trotter LE (1975) Vertex packings: Structural properties and algorithms. Math. Programming 8(1):232–248.Crossref, Google Scholar
• Ortega F, Wolsey LA (2003) A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41(3):143–158.Crossref, Google Scholar
• Özaltın OY, Hunsaker B, Schaefer AJ (2011) Predicting the solution time of branch-and-bound algorithms for mixed-integer programs. INFORMS J. Comput. 23(3):392–403.Link, Google Scholar
• Pfetsch ME (2008) Branch-and-cut for the maximum feasible subsystem problem. SIAM J. Optim. 19(1):21–38.Crossref, Google Scholar
• Picard JC, Queyranne M (1977) On the integer-valued packing problem variables in the linear vertex packing problem. Math. Programming 12:97–101.Crossref, Google Scholar
• Purdom PW (1978) Tree size by partial backtracking. SIAM J. Comput. 7(4):481–491.Crossref, Google Scholar
• Shinano Y, Achterberg T, Berthold T, Heinz S, Koch T (2012) ParaSCIP—A parallel extension of SCIP. Bischof C, Hegering HG, Nagel WE, Wittum G, eds. Competence High Performance Comput. 2010 (Springer, Berlin), 135–148.Google Scholar