Cutting plane selection is a subroutine used in all modern mixed-integer
linear programming solvers with the goal of selecting a subset of generated
cuts that induce optimal solver performance. These solvers have millions of
parameter combinations, and so are excellent candidates for parameter tuning.
Cut selection scoring rules are usually weighted sums of different
measurements, where the weights are parameters. We present a parametric family
of mixed-integer linear programs together with infinitely many family-wide
valid cuts. Some of these cuts can induce integer optimal solutions directly
after being applied, while others fail to do so even if an infinite amount are
applied. We show for a specific cut selection rule, that any finite grid search
of the parameter space will always miss all parameter values, which select
integer optimal inducing cuts in an infinite amount of our problems. We propose
a variation on the design of existing graph convolutional neural networks,
adapting them to learn cut selection rule parameters. We present a
reinforcement learning framework for selecting cuts, and train our design using
said framework over MIPLIB 2017 and a neural network verification data set. Our
framework and design show that adaptive cut selection does substantially
improve performance over a diverse set of instances, but that finding a single
function describing such a rule is difficult. Code for reproducing all
experiments is available at this https URL

本文研究了一种基于参数调整的混合整数线性规划问题的解法。通过设计一种基于图卷积神经网络和强化学习的自适应割集选择算法，我们证明此算法在实验中取得了优秀性能。