论文标题
在代表图形神经网络的混合构成线性程序时
On Representing Mixed-Integer Linear Programs by Graph Neural Networks
论文作者
论文摘要
虽然混合企业线性编程（MILP）通常是NP-HARD，但实用的MILP在过去二十年中获得了大约100倍的速度。尽管如此，随着尺寸的增加，许多类别的MILP迅速变得无法解决，激励研究人员寻求新的加速技术。通过深度学习，他们获得了强大的经验结果，并且通过将图形神经网络（GNN）应用于MILP解决方案过程的各个阶段做出决策，从而获得了许多结果。这项工作发现了一个基本限制：但是，所有GNN都将同样对待，这表明GNN缺乏表达一般的MILP的能力。然后，我们表明，通过将MILP限制为可展开的MILP或通过添加随机特征，存在可以可靠地预测MILP可行性，最佳目标值和最佳解决方案的GNN，以达到规定的精度。我们进行了小规模的数值实验，以验证我们的理论发现。
While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages of MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, indicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there exist GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision. We conducted small-scale numerical experiments to validate our theoretical findings.
