Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming
This addresses the problem of inefficient cut selection in MIP solvers for optimization practitioners, representing an incremental improvement over prior learning-based methods by incorporating broader contextual information.
The paper tackles the problem of cut selection in mixed-integer programming solvers by proposing Global Cut Selection (GCS), which uses a bipartite graph representation and combines graph neural networks with reinforcement learning to apply cuts across all nodes, resulting in significantly improved solving efficiency for synthetic and large-scale real-world MIPs compared to traditional and learning-based methods.
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 heuristics for cut plane selection but fail to leverage problem-specific structural features. Recent machine learning approaches use neural networks for cut selection but focus narrowly on the efficiency of single-node within the B&C algorithm, without considering the broader contextual information. To address this, we propose Global Cut Selection (GCS), which uses a bipartite graph to represent the search tree and combines graph neural networks with reinforcement learning to develop cut selection strategies. Unlike prior methods, GCS applies cutting planes across all nodes, incorporating richer contextual information. Experiments show GCS significantly improves solving efficiency for synthetic and large-scale real-world MIPs compared to traditional and learning-based methods.