Cut Selection in MILP based on Supervised Learning
S.C. Wang, Sheng-Jie Chen, Liang Chen · Procedia Computer Science · 2023
With the increasing popularity of deep learning techniques, there has been a growing interest in combining learning methods with Mixed-Integer Linear Programming (MILP) solving processes. A promising approach is to incorporate the learning model as a module in traditional methods. Cut selection is a fundamental subroutine in modern MILP solvers used to select a subset of generated cuts and enhance solver performance. In this work, we present a supervised learning framework to improve the effectiveness of cut selection. Cut selection scoring rules are typically weighted sums of different metrics, and we have developed weighted cut selection metrics based on Machine Learning (ML) techniques for different problems. We propose a novel Neural Network (NN) architecture that incorporates a Graph Convolutional Neural Network (GCN) with a self-attention mechanism to determine appropriate weights. The resulting model serves as a component of the solver and is evaluated through controlled experiments on real-world MILPs. The numerical results demonstrate that our approach outperforms the standard SCIP cut selection strategy, especially on datasets containing the same class of problems.