Learning to Select Cuts for Efficient Mixed-Integer Programming
- URL: http://arxiv.org/abs/2105.13645v1
- Date: Fri, 28 May 2021 07:48:34 GMT
- Title: Learning to Select Cuts for Efficient Mixed-Integer Programming
- Authors: Zeren Huang, Kerong Wang, Furui Liu, Hui-ling Zhen, Weinan Zhang,
Mingxuan Yuan, Jianye Hao, Yong Yu, Jun Wang
- Abstract summary: 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.
- Score: 46.60355046375608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Cutting plane methods play a significant role in modern solvers for tackling
mixed-integer programming (MIP) problems. Proper selection of cuts would remove
infeasible solutions in the early stage, thus largely reducing the
computational burden without hurting the solution accuracy. However, the major
cut selection approaches heavily rely on heuristics, which strongly depend on
the specific problem at hand and thus limit their generalization capability. In
this paper, we propose a data-driven and generalizable cut selection approach,
named Cut Ranking, in the settings of multiple instance learning. To measure
the quality of the candidate cuts, a scoring function, which takes the
instance-specific cut features as inputs, is trained and applied in cut ranking
and selection. In order to evaluate our method, we conduct extensive
experiments on both synthetic datasets and real-world datasets. Compared with
commonly used heuristics for cut selection, the learning-based policy has shown
to be more effective, and is capable of generalizing over multiple problems
with different properties. Cut Ranking has been deployed in an industrial
solver for large-scale MIPs. In the online A/B testing of the product planning
problems with more than $10^7$ variables and constraints daily, Cut Ranking has
achieved the average speedup ratio of 12.42% over the production solver without
any accuracy loss of solution.
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 to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming [61.59888010725235]
Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs)
We propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies.
HEM is the first data-driven methodology that tackles well (P1)-(P3) simultaneously.
arXiv Detail & Related papers (2024-04-19T05:40:25Z) - Learning Cut Selection for Mixed-Integer Linear Programming via
Hierarchical Sequence Model [81.56473654324328]
We propose a novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning.
HEM is the first method that can tackle (P1)-(P3) in cut selection simultaneously from a data-driven perspective.
Experiments show that HEM significantly improves the efficiency of solving MILPs compared to human-designed and learning-based baselines.
arXiv Detail & Related papers (2023-02-01T04:59:55Z) - 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) - 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) - 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 Schedule Heuristics in Branch-and-Bound [25.79025327341732]
Real-world applications typically require finding good solutions early in the search to enable fast decision-making.
We propose the first data-driven framework for schedulings in an exact MIP solver.
Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
arXiv Detail & Related papers (2021-03-18T14:49:52Z) - ABM: an automatic supervised feature engineering method for loss based
models based on group and fused lasso [0.0]
A vital problem in solving classification or regression problem is to apply feature engineering and variable selection on data before fed into models.
This paper proposes an end-to-end supervised cutting point selection method based on group and lasso fused along with the automatically variable selection effect.
arXiv Detail & Related papers (2020-09-22T12:42:22Z)
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.