2026-06-01T23:11:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16632 2024-03-06T10:57:55Z ddc:004 open_access

Improved Sample Complexity Bounds for Branch-And-Cut Balcan, Maria-Florina Prasad, Siddharth Sandholm, Tuomas Vitercik, Ellen Automated algorithm configuration integer programming machine learning theory tree search branch-and-bound branch-and-cut cutting planes sample complexity generalization guarantees data-driven algorithm design The branch-and-cut algorithm for integer programming has a wide variety of tunable parameters that have a huge impact on its performance, but which are challenging to tune by hand. An increasingly popular approach is to use machine learning to configure these parameters based on a training set of integer programs from the application domain. We bound how large the training set should be to ensure that for any configuration, its average performance over the training set is close to its expected future performance. Our guarantees apply to parameters that control the most important aspects of branch-and-cut: node selection, branching constraint selection, and cut selection, and are sharper and more general than those from prior research. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maria-Florina Balcan and Siddharth Prasad and Tuomas Sandholm and Ellen Vitercik 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.3 urn:nbn:de:0030-drops-166321 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.3 eng https://creativecommons.org/licenses/by/4.0/legalcode