论文标题
改善基于问题的混合整数编程问题的原始启发式方法：一种基于学习的方法
Improving Primal Heuristics for Mixed Integer Programming Problems based on Problem Reduction: A Learning-based Approach
论文作者
论文摘要
在本文中，我们提出了一个基于双层预测的还原分支（BP-RB）框架，以加快寻找高质量可行解决方案的混合整数编程（MIP）问题的过程。使用图形卷积网络（GCN）来预测二进制变量的值。之后，通过以预测概率为条件的贪婪方法将二进制变量的子集固定在预测值上。通过探索逻辑后果，提出了一种基于学习的问题减少方法，从而大大降低了变量和约束大小。对于还原性子-MIP问题，第二层GCN框架被用来更新其余二进制变量值的预测，并确定随后用于分支的变量的选择来生成分支和绑定（B＆B）树。数值示例表明，我们的BP-RB框架加快了原始的启发式，并找到了高质量的可行解决方案。
In this paper, we propose a Bi-layer Predictionbased Reduction Branch (BP-RB) framework to speed up the process of finding a high-quality feasible solution for Mixed Integer Programming (MIP) problems. A graph convolutional network (GCN) is employed to predict binary variables' values. After that, a subset of binary variables is fixed to the predicted value by a greedy method conditioned on the predicted probabilities. By exploring the logical consequences, a learning-based problem reduction method is proposed, significantly reducing the variable and constraint sizes. With the reductive sub-MIP problem, the second layer GCN framework is employed to update the prediction for the remaining binary variables' values and to determine the selection of variables which are then used for branching to generate the Branch and Bound (B&B) tree. Numerical examples show that our BP-RB framework speeds up the primal heuristic and finds the feasible solution with high quality.
