Improved Learning Bounds for Branch-and-Cut

• URL: http://arxiv.org/abs/2111.11207v1
• Date: Thu, 18 Nov 2021 04:07:29 GMT
• Title: Improved Learning Bounds for Branch-and-Cut
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract summary: Branch-and-cut is the most widely used algorithm for solving integer programs. An increasingly popular approach is to use machine learning to tune these parameters. In this paper, we prove sample guarantees for this procedure.
• Score: 98.92725321081994
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branch-and-cut is the most widely used algorithm for solving integer programs, employed by commercial solvers like CPLEX and Gurobi. Branch-and-cut has a wide variety of tunable parameters that have a huge impact on the size of the search tree that it builds, but are challenging to tune by hand. An increasingly popular approach is to use machine learning to tune these parameters: using a training set of integer programs from the application domain at hand, the goal is to find a configuration with strong predicted performance on future, unseen integer programs from the same domain. If the training set is too small, a configuration may have good performance over the training set but poor performance on future integer programs. In this paper, we prove sample complexity guarantees for this procedure, which 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 cutting plane selection, and are sharper and more general than those found in prior research.

Related papers

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems. Recent advances have employed a data-driven approach to select optimal cutting planes from a parameterized family. We show that the selected CGF can outperform the GMI cuts for certain distributions.
  arXiv  Detail & Related papers  (2024-05-22T20:56:34Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  Linear Programs (ILPs) are powerful tools for modeling and solving a large number of optimization problems. Large Neighborhood Search (LNS), as a algorithm, can find high quality solutions to ILPs faster than Branch and Bound. We propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics.
  arXiv  Detail & Related papers  (2023-02-03T07:15:37Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut.
  arXiv  Detail & Related papers  (2022-04-15T03:32:40Z)
• AdaGrid: Adaptive Grid Search for Link Prediction Training Objective [58.79804082133998]
  Training objective crucially influences the model's performance and generalization capabilities. We propose Adaptive Grid Search (AdaGrid) which dynamically adjusts the edge message ratio during training. We show that AdaGrid can boost the performance of the models up to $1.9%$ while being nine times more time-efficient than a complete search.
  arXiv  Detail & Related papers  (2022-03-30T09:24:17Z)
• Adaptive Cut Selection in Mixed-Integer Linear Programming [0.294944680995069]
  Cut selection is a subroutine used in all modern mixed-integer linear programming solvers. We present a family of mixed-integer linear programs together with infinitely many family-wide valid cuts. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values.
  arXiv  Detail & Related papers  (2022-02-22T15:07:33Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm. We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
  arXiv  Detail & Related papers  (2021-06-08T00:57:59Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  We propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. It has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
  arXiv  Detail & Related papers  (2021-05-28T07:48:34Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.