用神经网络替代传统求解器，加速最大割问题的精确求解。
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
- 设计专用图神经网络，直接预测满足约束的半定规划解。
- 实验表明可降低10.6倍的计算开销，媲美顶级求解器性能。
- 无需真实解作标签，自监督训练即可，适合结构化优化场景。
精确求解难解组合优化问题通常依赖强凸松弛，但反复求解这些松弛在分支定界算法中代价高昂。针对最大割问题，我们提出一种专用图神经网络，作为半定规划（SDP）求解器的轻量级神经代理，可直接嵌入精确分支定界框架。该架构复杂度为$/mathcal{O}(n^2 + ne)$，能同时输出原始和对偶可行的SDP解。原始解通过Goemans--Williamson算法生成可行最大割解。模型采用自监督训练，无需真实求解的SDP结果作为标签。实验证明，与最先进的SDP求解器Mosek相比，本方法可将边界计算成本降低高达10.6倍。研究展示了学习型、可行性保持代理在加速结构化凸松弛精确优化中的潜力。
原文摘要 · Abstract (English)
Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for Max-Cut, where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity $\mathcal{O}(n^2 + ne)$, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 \times$ compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。