Adaptive Cut Selection in Mixed-Integer Linear Programming
- URL: http://arxiv.org/abs/2202.10962v1
- Date: Tue, 22 Feb 2022 15:07:33 GMT
- Title: Adaptive Cut Selection in Mixed-Integer Linear Programming
- Authors: Mark Turner, Thorsten Koch, Felipe Serrano, Michael Winkler
- Abstract summary: 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.
- Score: 0.294944680995069
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cut selection is a subroutine used in all modern mixed-integer linear
programming solvers with the goal of selecting a subset of generated cuts that
induce optimal solver performance. These solvers have millions of parameter
combinations, and so are excellent candidates for parameter tuning. Cut
selection scoring rules are usually weighted sums of different measurements,
where the weights are parameters. We present a parametric family of
mixed-integer linear programs together with infinitely many family-wide valid
cuts. Some of these cuts can induce integer optimal solutions directly after
being applied, while others fail to do so even if an infinite amount are
applied. We show for a specific cut selection rule, that any finite grid search
of the parameter space will always miss all parameter values, which select
integer optimal inducing cuts in an infinite amount of our problems. We propose
a variation on the design of existing graph convolutional neural networks,
adapting them to learn cut selection rule parameters. We present a
reinforcement learning framework for selecting cuts, and train our design using
said framework over MIPLIB 2017. Our framework and design show that adaptive
cut selection does substantially improve performance over a diverse set of
instances, but that finding a single function describing such a rule is
difficult. Code for reproducing all experiments is available at
https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.
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) - 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) - 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) - 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) - 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) - 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) - Feature Selection Methods for Cost-Constrained Classification in Random
Forests [3.4806267677524896]
Cost-sensitive feature selection describes a feature selection problem, where features raise individual costs for inclusion in a model.
Random Forests define a particularly challenging problem for feature selection, as features are generally entangled in an ensemble of multiple trees.
We propose Shallow Tree Selection, a novel fast and multivariate feature selection method that selects features from small tree structures.
arXiv Detail & Related papers (2020-08-14T11:39:52Z)
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.