Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization

• URL: http://arxiv.org/abs/2311.03350v3
• Date: Thu, 9 Nov 2023 17:19:56 GMT
• Title: Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization
• Authors: Gabriele Dragotto, Stefan Clarke, Jaime Fern\'andez Fisac, Bartolomeo Stellato
• Abstract summary: 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.
• Score: 1.7398512809572197
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider the problem of solving a family of parametric mixed-integer linear optimization problems where some entries in the input data change. We introduce the concept of cutting-plane layer (CPL), i.e., a differentiable cutting-plane generator mapping the problem data and previous iterates to cutting planes. 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. In an offline phase, we train our algorithm by updating the internal parameters controlling the CPLs, thus altering cut generation. Once trained, our algorithm computes, with predictable execution times and a fixed number of cuts, solutions with low integrality gaps. Preliminary computational tests show that our algorithm generalizes on unseen instances and captures underlying parametric structures.

Related papers

• Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
  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.
  arXiv  Detail & Related papers  (2024-06-26T22:50:43Z)
• 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)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• 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)
• Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
  We study techniques to develop efficient learning algorithms for data-driven algorithm design. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
  arXiv  Detail & Related papers  (2022-04-07T17:27:18Z)
• Accelerated nonlinear primal-dual hybrid gradient algorithms with applications to machine learning [0.0]
  primal-dual hybrid gradient (PDHG) is a first-order method that splits convex optimization problems with saddle-point structure into smaller subproblems. PDHG requires stepsize parameters fine-tuned for the problem at hand. We introduce accelerated nonlinear variants of the PDHG algorithm that can achieve, for a broad class of optimization problems relevant to machine learning.
  arXiv  Detail & Related papers  (2021-09-24T22:37:10Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Stochastic Cutting Planes for Data-Driven Optimization [6.243995448840211]
  We show that the algorithm is able to converge to an $epsilon$optimal solution with high probability. We experimentally explore the lower limits of sampling for cutting planes and show that for many problems, a sampling size of $O(sqrt[3]n)$ appears to be sufficient for high quality solutions.
  arXiv  Detail & Related papers  (2021-03-03T16:21:32Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)

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.