Learning Cut Generating Functions for Integer Programming

• URL: http://arxiv.org/abs/2405.13992v1
• Date: Wed, 22 May 2024 20:56:34 GMT
• Title: Learning Cut Generating Functions for Integer Programming
• Authors: Hongyu Cheng, Amitabh Basu,
• Abstract summary: 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.
• Score: 1.1510009152620668
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of cutting planes which are derived constraints that reduce the search space for an optimal solution. Selecting effective cutting planes to produce small branch-and-cut trees is a critical challenge in the branch-and-cut algorithm. Recent advances have employed a data-driven approach to select optimal cutting planes from a parameterized family, aimed at reducing the branch-and-bound tree size (in expectation) for a given distribution of integer programming instances. We extend this idea to the selection of the best cut generating function (CGF), which is a tool in the integer programming literature for generating a wide variety of cutting planes that generalize the well-known Gomory Mixed-Integer (GMI) cutting planes. We provide rigorous sample complexity bounds for the selection of an effective CGF from certain parameterized families that provably performs well for any specified distribution on the problem instances. Our empirical results show that the selected CGF can outperform the GMI cuts for certain distributions. Additionally, we explore the sample complexity of using neural networks for instance-dependent CGF selection.

Related papers

• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  We consider a joint device selection and aggregate beamforming design with the objectives of minimizing the aggregate error and maximizing the number of selected devices. To tackle the problems in a cost-effective manner, we propose a random aggregate beamforming-based scheme. We additionally use analysis to study the obtained aggregate error and the number of the selected devices when the number of devices becomes large.
  arXiv  Detail & Related papers  (2024-02-20T23:59:45Z)
• 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)
• Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
  Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. Running the dualPs at the nodes of the branch-and-bound tree is computationally cumbersome due to the number of node candidates and the lack of a priori knowledge on which nodes admit useful cutting planes. We propose a novel framework based on learning to approximate the optimal value of a machineP class that determines whether a cutting plane can be generated at a node of the branch-bound tree.
  arXiv  Detail & Related papers  (2023-10-30T18:31:52Z)
• 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)
• 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)
• 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)
• 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)
• 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.