无需训练数据，用强化学习优化最大割问题的超平面取样策略。
A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut
- 基于非周期强化学习，让智能体自主选择更优超平面。
- 在不同密度的大规模图上，切割结果均优于经典GW算法。
- 适合需要高精度且无标注数据的图优化场景。
最大割（MaxCut）问题是NP完全的，其最优解在最坏情况下为NP难。因此，通常采用依赖领域知识的启发式算法。近年来，基于大规模（未）标记数据的学习方法被提出，但普遍存在泛化性和可扩展性不足的问题。经典的Goemans-Williamson（GW）算法将二次无约束二值优化（QUBO）松弛为半定规划（SDP），再通过均匀采样随机超平面进行超平面取样，将SDP解转化为节点二值分配。本文提出一种无需训练数据的强化学习方法，基于非周期强化学习框架，使智能体学习选择能产生更优切割的超平面，通过在马尔可夫决策过程（MDP）上优化，该方法在具有不同密度和度分布的大规模图上始终优于GW算法。
原文摘要 · Abstract (English)
The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。