Learning to Remove Cuts in Integer Linear Programming

• URL: http://arxiv.org/abs/2406.18781v1
• Date: Wed, 26 Jun 2024 22:50:43 GMT
• Title: Learning to Remove Cuts in Integer Linear Programming
• Authors: Pol Puigdemont, Stratis Skoulakis, Grigorios Chrysos, Volkan Cevher,
• Abstract summary: We consider the removal of previous cuts introduced at any of the preceding iterations of a method under a learnable parametric criteria. We demonstrate that in fundamental optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies.
• Score: 57.15699051569638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.

Related papers

• Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
  We study the assortment optimization problem under the mixed-logit customer choice model. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex.
  arXiv  Detail & Related papers  (2024-07-26T06:27:11Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• 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)
• Cutting Plane Selection with Analytic Centers and Multiregression [2.8757106397019228]
  We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space.
  arXiv  Detail & Related papers  (2022-12-14T14:06:27Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection. We propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert.
  arXiv  Detail & Related papers  (2022-06-27T16:07:27Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  We propose a novel solution for challenging non-problems of multiple variables. Our proposed approach is able to achieve effective iterations in cases while other methods would typically fail.
  arXiv  Detail & Related papers  (2020-09-09T10:45:00Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

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.