A recent Graph Neural Network (GNN) approach for learning to branch has been
shown to successfully reduce the running time of branch-and-bound algorithms
for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for
inference, MILP solvers are purely CPU-based. This severely limits its
application as many practitioners may not have access to high-end GPUs. In this
work, we ask two key questions. First, in a more realistic setting where only a
CPU is available, is the GNN model still competitive? Second, can we devise an
alternate computationally inexpensive model that retains the predictive power
of the GNN architecture? We answer the first question in the negative, and
address the second question by proposing a new hybrid architecture for
efficient branching on CPU machines. The proposed architecture combines the
expressive power of GNNs with computationally inexpensive multi-layer
perceptrons (MLP) for branching. We evaluate our methods on four classes of
MILP problems, and show that they lead to up to 26% reduction in solver running
time compared to state-of-the-art methods without a GPU, while extrapolating to
harder problems than it was trained on. The code for this project is publicly
available at this https URL

本文提出了一种基于 GNN 和 MLP 的混合模型，可在没有高端 GPU 的情况下有效地优化 Mixed Integer Linear Programming 问题求解器的性能。