Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), as they significantly tighten the dual bounds and improve the solving performance. A key problem for cuts is when to stop cuts generation, which is important for the efficiency of solving MILPs. However, many modern MILP solvers employ hard-coded heuristics to tackle this problem, which tends to neglect underlying patterns among MILPs from certain applications. To address this challenge, we formulate the cuts generation stopping problem as a reinforcement learning problem and propose a novel hybrid graph representation model (HYGRO) to learn effective stopping strategies. An appealing feature of HYGRO is that it can effectively capture both the dynamic and static features of MILPs, enabling dynamic decision-making for the stopping strategies. To the best of our knowledge, HYGRO is the first data-driven method to tackle the cuts generation stopping problem. By integrating our approach with modern solvers, experiments demonstrate that HYGRO significantly improves the efficiency of solving MILPs compared to competitive baselines, achieving up to 31% improvement.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingSimilar Papers 제목 키워드 기반
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 …
Molecular Design Based on Artificial Neural Networks, Integer Programming and Grid Neighbor Search
A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In the…
FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming
Mixed-Integer Linear Programming (MILP) is a foundational tool for complex decision-making problems. However, the NP-hard nature of MILP presents a significant computational challenge, motivating the development of machi…
Trajectory planning with a dynamic obstacle clustering strategy using Mixed-Integer Linear Programming
In this paper we propose a technique that assigns obstacles to clusters used for collision avoidance via Mixed-Integer Programming. This strategy enables a reduction in the number of binary variables used for collision a…
ClusteringCollision AvoidanceModel Predictive ControlTrajectory PlanningReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by…