Recently, machine learning, particularly message-passing graph neural
networks (MPNNs), has gained traction in enhancing exact optimization
algorithms. For example, MPNNs speed up solving mixed-integer optimization
problems by imitating computational intensive heuristics like strong branching,
which entails solving multiple linear optimization problems (LPs). Despite the
empirical success, the reasons behind MPNNs' effectiveness in emulating linear
optimization remain largely unclear. Here, we show that MPNNs can simulate
standard interior-point methods for LPs, explaining their practical success.
Furthermore, we highlight how MPNNs can serve as a lightweight proxy for
solving LPs, adapting to a given problem instance distribution. Empirically, we
show that MPNNs solve LP relaxations of standard combinatorial optimization
problems close to optimality, often surpassing conventional solvers and
competing approaches in solving time.

机器学习中的消息传递图神经网络（MPNNs）可以模拟线性优化问题和组合优化问题，提高解决难解优化问题的效率。

探索图神经网络求解线性优化问题的能力

Exploring the Power of Graph Neural Networks in Solving Linear  Optimization Problems

In many applications, when building linear regression models, it is important
to account for the presence of outliers, i.e., corrupted input data points.
Such problems can be formulated as mixed-integer optimization problems
involving cubic terms, each given by the product of a binary variable and a
quadratic term of the continuous variables. Existing approaches in the
literature, typically relying on the linearization of the cubic terms using
big-M constraints, suffer from weak relaxation and poor performance in
practice. In this work we derive stronger second-order conic relaxations that
do not involve big-M constraints. Our computational experiments indicate that
the proposed formulations are several orders-of-magnitude faster than existing
big-M formulations in the literature for this problem.

本论文提出了使用二阶锥松弛方法来解决具有离群值时使用线性回归模型所遇到的混合整数优化问题，相比于现有方法使用的大 M 约束进行的线性化，该方法具有更强的弛豫度且性能更优。