Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

• URL: http://arxiv.org/abs/2204.07312v1
• Date: Fri, 15 Apr 2022 03:32:40 GMT
• Title: Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract summary: 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.
• Score: 88.94020638263467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete optimization problems and thus have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming. 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. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.

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)
• Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming [11.293025183996832]
  Mixed Linear Programming (MILP) offers a powerful modeling language for a wide range of applications. In recent years, there has been an explosive development in the use of machine learning algorithms for enhancing all main tasks involved in the branch-and-bound algorithm. In particular, we give detailed attention to machine learning algorithms that automatically optimize some metric of branch-and-bound efficiency.
  arXiv  Detail & Related papers  (2024-02-08T09:19:26Z)
• Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization [1.7398512809572197]
  We consider the problem of solving a family of parametric mixed-integer linear optimization problems where some entries in the input data change. We propose a CPL implementation to generate split cuts, and by combining several CPLs, we devise a differentiable cutting-plane algorithm that exploits the repeated nature of parametric instances.
  arXiv  Detail & Related papers  (2023-11-06T18:57:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  We generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers. Our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark.
  arXiv  Detail & Related papers  (2022-08-11T10:31:28Z)
• Improved Learning Bounds for Branch-and-Cut [98.92725321081994]
  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.
  arXiv  Detail & Related papers  (2021-11-18T04:07:29Z)
• 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)

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.