A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming
The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.
Code (1)
Similar Papers 제목 키워드 기반
Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming
In mixed-integer programming (MIP) solvers, cutting planes are essential for Branch-and-Cut (B&C) algorithms as they reduce the search space and accelerate the solving process. Traditional methods rely on hard-coded heur…
Learning to Configure Separators in Branch-and-Cut
Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of c…
ManagementSample Complexity of Tree Search Configuration: Cutting Planes and Beyond
Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search alg…
Variable SelectionLearning Cut Generating Functions for Integer Programming
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 reduc…
Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization
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 differentia…