Abstract
A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aardal, K., Lenstra, A.: Hard equality constrained integer knapsacks. Math. Oper. Res. 29, 724–738 (2004)
Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)
Basu, A., Conforti, M., Di Summa, M., Jiang, H.: Complexity of branch-and-bound and cutting planes in mixed-integer optimization - II. In: Singh, M., Williamson, D.P. (eds.) IPCO 2021. LNCS, vol. 12707, pp. 383–398. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-73879-2_27
Beame, P., et al.: Stabbing planes. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 94, pp. 10:1–10:20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.ITCS.2018.10, http://drops.dagstuhl.de/opus/volltexte/2018/8341
Bixby, R.: Solving real-world linear programs: a decade and more of progress. Oper. Res. 50(1), 3–15 (2002)
Bixby, R., Boyd, E., Indovina, R.: MIPLIB: a test set of mixed integer programming problems. SIAM News (1992)
Cheung, K.K.H., Gleixner, A., Steffy, D.E.: Verifying integer programming results. In: Eisenbrand, F., Koenemann, J. (eds.) IPCO 2017. LNCS, vol. 10328, pp. 148–160. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59250-3_13
Chvátal, V.: Hard knapsack problems. Oper. Res. 28, 1402–1411 (1980)
Cornuéjols, G., Liberti, L., Nannicini, G.: Improved strategies for branching on general disjunctions. Math. Program. 130, 225–247 (2011)
Dadush, D., Tiwari, S.: On the complexity of branching proofs. In: Saraf, S. (ed.) 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 169, pp. 34:1–34:35. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl (2020)
Dey, S., Dubey, Y., Molinaro, M.: Lower bounds on the size of general branch-and-bound trees. Math. Program. (2022)
Dey, S., Dubey, Y., Molinaro, M., Shah, P.: A theoretical and computational analysis of full strong-branching. arXiv:2110.10754 (2021)
Dunning, I., Huchette, J., Lubin, M.: Jump: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295–320 (2017). https://doi.org/10.1137/15M1020575
Fischetti, M., Monaci, M.: Backdoor branching. INFORMS J. Comput. 25(4), 693–700 (2018)
Gamrath, G., Melchiori, A., Berthold, T., Gleixner, A.M., Salvagnin, D.: Branching on multi-aggregated variables. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 141–156. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18008-3_10
Gläser, M., Pfetsch, M.: On the complexity of finding shortest variable disjunction branch-and-bound proofs. In: Aardal, K., Sanità, L. (eds.) IPCO 2022. LNCS, vol. 13265, pp. 291–304. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06901-7_22
Gurobi Optimization: Gurobi Optimizer (Version 9.5). https://www.gurobi.com/products/gurobi-optimizer/. Accessed 4 Nov 2022
Jeroslow, R.: Trivial integer programs unsolvble by branch-and-bound. Math. Program. 6, 105–109 (1974)
Karamanov, M., Cornuéjols, G.: Branching on general disjunctions. Math. Program. 128, 403–436 (2011)
Khalil, E., Vaezipoor, P., Dilkina, B.: Finding backdoors to integer programs: a Monte Carlo tree search framework. In: Proceedings of AAAI (2022)
Legat, B., Dowson, O., Dias Garcia, J., Lubin, M.: MathOptInterface: a data structure for mathematical optimization problems. INFORMS J. Comput. 34(2), 672–689 (2021). https://doi.org/10.1287/ijoc.2021.1067
Linderoth, J., Savelsbergh, M.: A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2), 173–187 (1999)
Mahajan, A., Ralphs, T.: Experiments with branching using general disjunctions. In: Proceedings of Operations Research and Cyber-Infrastructure, pp. 101–118 (2009)
Mahajan, A., Ralphs, T.: On the complexity of selecting disjunctions in integer programming. SIAM J. Optim. 20(5), 2181–2198 (2010)
Mahmoud, H., Chinneck, J.: Achieving MILP feasibility quickly using general disjunctions. Comput. Oper. Res. 40, 2094–2102 (2013)
Mehrotra, S., Li, Z.: Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices. J. Glob. Optim. (2010)
Owen, J., Mehrotra, S.: Experimental results on using general disjunctions in branch-and-bound for general-integer linear programs. Comput. Optim. Appl. 20, 159–170 (2001)
Walter, M.: Sparsity of lift-and-project cutting planes. In: Helber, S., et al. (eds.) Operations Research Proceedings 2012, pp. 9–14. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-00795-3_2
Xavier, A.S., Qiu, F.: MIPLearn: a framework for learning-enhanced mixed-integer optimization (Julia interface) (2022). https://github.com/ANL-CEEESA/MIPLearn.jl
Yang, Y., Boland, N., Savelsbergh, M.: Multivariable branching: a 0–1 knapsack problem case study. INFORMS J. Comput. 33(4), 1354–1367 (2021)
Acknowledgements
J. Paat was supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant [RGPIN-2021-02475]. Á.S. Xavier was partially supported by the U.S. Department of Energy Office of Electricity. The authors want to thank the referees, whose comments improved the overall presentation of the paper, led to better bounds in Theorem 2, and identified directions of future work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Muñoz, G., Paat, J., Xavier, Á.S. (2023). Compressing Branch-and-Bound Trees. In: Del Pia, A., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2023. Lecture Notes in Computer Science, vol 13904. Springer, Cham. https://doi.org/10.1007/978-3-031-32726-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-32726-1_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32725-4
Online ISBN: 978-3-031-32726-1
eBook Packages: Computer ScienceComputer Science (R0)