用学习方法优化组合优化算法参数，提升求解质量与效率。
Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization
- 用图神经网络预测近似算法参数，实现端到端自监督训练。
- 在旅行商问题和最小k-cut问题上达到顶尖求解水平。
- 适合需要快速高质量解的工业场景，如物流与制造。
组合优化（CO）问题广泛存在于医疗、物流和制造等领域。尽管精确解通常计算成本过高，但实际应用常需在时间预算内获得高质量解。为此，我们提出一种基于学习的方法，改进现有非学习型近似算法。具体而言，将这些近似算法参数化，并训练图神经网络（GNN）预测能产生接近最优解的参数值。方法采用新颖的梯度估计方案，在无需算法内部结构信息的前提下，将近似算法视为黑盒进行端到端自监督训练。该方法融合了学习与传统算法的优势：GNN从数据中学习以引导算法向更优解收敛，而近似算法保障解的可行性。我们在两个经典组合优化问题——旅行商问题（TSP）和最小k-cut问题上验证了该方法，结果表明其性能可媲美当前最先进的学习型求解器。
原文摘要 · Abstract (English)
Combinatorial optimization (CO) problems arise across a broad spectrum of domains, including medicine, logistics, and manufacturing. While exact solutions are often computationally infeasible, many practical applications require high-quality solutions within a given time budget. To address this, we propose a learning-based approach that enhances existing non-learned approximation algorithms for CO. Specifically, we parameterize these approximation algorithms and train graph neural networks (GNNs) to predict parameter values that yield near-optimal solutions. Our method is trained end-to-end in a self-supervised fashion, using a novel gradient estimation scheme that treats the approximation algorithm as a black box. This approach combines the strengths of learning and traditional algorithms: the GNN learns from data to guide the algorithm toward better solutions, while the approximation algorithm ensures feasibility. We validate our method on two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the minimum k-cut problem. Our results demonstrate that the proposed approach is competitive with state-of-the-art learned CO solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。