论文标题
MIP-GNN：用于指导组合求解器的数据驱动框架
MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
论文作者
论文摘要
混合企业编程（MIP）技术提供了一种通用的方法来制定和解决组合优化问题。尽管通常可靠，但最先进的MIP求解器以手工制作的启发式方法为基础，许多关键的决定在很大程度上忽略了感兴趣问题的给定实例分布中的共同模式。在这里，我们提出了MIP-GNN，这是一种通过数据驱动的见解来增强此类求解器的一般框架。通过编码给定的混合构成线性程序（MILP）作为两部分图形的可变构成相互作用，我们利用最新的图形神经网络体系结构来预测可变偏见，即（即接近）最佳解决方案的组件平均值，表明可变的可能性可能会在（接近）中（近）设置为最佳解决方案。反过来，使用单个曾经训练的模型引起的预测偏见是指导求解器，以取代启发式组件。我们将MIP-GNN集成到最先进的MIP求解器中，将其应用于节点选择和热身启动等任务，与在两类具有挑战性的二进制MILP的默认设置相比，显示出显着改进。
Mixed-integer programming (MIP) technology offers a generic way of formulating and solving combinatorial optimization problems. While generally reliable, state-of-the-art MIP solvers base many crucial decisions on hand-crafted heuristics, largely ignoring common patterns within a given instance distribution of the problem of interest. Here, we propose MIP-GNN, a general framework for enhancing such solvers with data-driven insights. By encoding the variable-constraint interactions of a given mixed-integer linear program (MILP) as a bipartite graph, we leverage state-of-the-art graph neural network architectures to predict variable biases, i.e., component-wise averages of (near) optimal solutions, indicating how likely a variable will be set to 0 or 1 in (near) optimal solutions of binary MILPs. In turn, the predicted biases stemming from a single, once-trained model are used to guide the solver, replacing heuristic components. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting, showing significant improvements compared to the default setting of the solver on two classes of challenging binary MILPs.
