Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning
Cutting planes are essential for solving mixed-integer linear problems
(MILPs), because they facilitate bound improvements on the optimal solution
value. For selecting cuts, modern solvers rely on manually designed heuristics
that are tuned to gauge the potential effectiveness of cuts. 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 - but is too
expensive to be deployed in practice. In response, we propose a new neural
architecture (NeuralCut) for imitation learning on the lookahead expert. Our
model outperforms standard baselines for cut selection on several synthetic
MILP benchmarks. Experiments with a B&C solver for neural network verification
further validate our approach, and exhibit the potential of learning methods in
this setting.