Learning to select cuts for efficient mixed-integer programming

作者：

Highlights：

• We propose an efficient and generalizable learning based cut selection policy for tackling combinatorial optimization problems.

• We present a novel cut ranking formulation in the context of multiple instance learning.

• Experiments demonstrate that cut ranking is superior to other manual heuristics and can generalize to problems of different properties

• Experiments on real-world product planning problems of an industrial MIP solver demonstrate that cut ranking can significantly improve the efficiency.

摘要

•We propose an efficient and generalizable learning based cut selection policy for tackling combinatorial optimization problems.•We present a novel cut ranking formulation in the context of multiple instance learning.•Experiments demonstrate that cut ranking is superior to other manual heuristics and can generalize to problems of different properties•Experiments on real-world product planning problems of an industrial MIP solver demonstrate that cut ranking can significantly improve the efficiency.

论文关键词：Mixed-Integer programming,Cutting plane,Multiple instance learning,Generalization ability

论文评审过程：Received 1 April 2021, Revised 23 September 2021, Accepted 25 September 2021, Available online 4 October 2021, Version of Record 18 October 2021.

论文官网地址：https://doi.org/10.1016/j.patcog.2021.108353