論文の概要: Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2605.07113v1
• Date: Fri, 08 May 2026 01:41:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.725937
• Title: Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
• Title（参考訳）: フェーザビリティ保護型グラフニューラルネットワークによる大域的最適解法
• Authors: Hao Chen, Chendi Qian, Christopher Morris, Andrea Lodi, Can Li,
• Abstract要約: SDPソルバの原理的,軽量なニューラルプロキシとして機能する,Max-Cut固有のグラフニューラルネットワークを提案する。 我々のアーキテクチャは、最先端のSDPソルバであるMosekと比較して、正確なMax-Cut解のバウンディングコストを最大10.6ドル削減できることを示す。
• 参考スコア（独自算出の注目度）: 20.951741111898897
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: 厳密な組合せ最適化問題の厳密な解法は、しばしば強い凸緩和に依存するが、分岐とバウンドのアルゴリズム内で繰り返しこの緩和を解くことは、違法に高価である。 したがって、分岐とバウンドが半有限プログラミング(SDP)緩和を有界なサブプロブレムに使用するMax-Cutのこの課題を考える。 我々は、これらのSDPソルバの原理的かつ軽量なニューラルプロキシとして機能し、正確に分岐とバウンドのフレームワークに直接接続できるMax-Cut固有のグラフニューラルネットワークを提案する。 提案したアーキテクチャは、複雑さのステップを$\mathcal{O}(n^2 + ne)$で更新し、原始的および二重実現可能なSDPソリューションの両方を予測する。 原始SDP解はゴーマンス-ウィリアムソンアルゴリズムによって実現可能なマックス・カット解が得られる。 また、ラベルとして解決されたSDP緩和を必要とせず、自己指導型で訓練する。 経験的に、我々のアーキテクチャは、最先端のSDPソルバであるMosekと比較して、正確なMax-Cut解のバウンディングコストを最大10.6 \times$で大幅に削減できることを示す。 我々の研究は、構造化凸緩和に対する正確な最適化を加速するための、学習し、有効に保存するサロゲートの可能性を強調している。

関連論文リスト

• On the Expressive Power of GNNs to Solve Linear SDPs [11.574125752787156]
  半有限プログラム(SDP)は凸最適化のための強力なフレームワークである。 本研究では, 最適SDP解の回復に有効な表現力について検討する。 我々は、SDPのキー構造を捉える表現力のあるアーキテクチャを特定し、特に標準一階解決器の更新をエミュレートする。
  論文  参考訳（メタデータ） (2026-04-30T12:29:14Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut [13.43661547732185]
  エージェントが改良された丸みを帯びた超平面を選択し、ゴーマンス・ウィリアムソン(GW)アルゴリズムで生成されたものよりも優れたカットを得られるように学習する、非エポゾディック強化学習の定式化に基づくトレーニングデータフリーアプローチを提案する。 提案手法は, 密度や次数分布の異なる大規模グラフに対して, より優れたカットを一貫して達成する。
  論文  参考訳（メタデータ） (2025-05-19T17:41:10Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-05-28T18:07:16Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。