論文の概要: Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2511.19573v1
• Date: Mon, 24 Nov 2025 17:51:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.10358
• Title: Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
• Title（参考訳）: 構造によるニューラルトラクタビリティ:グラフ組合せ最適化のための学習補助アルゴリズム
• Authors: Jialiang Li, Weitong Chen, Mingyu Guo,
• Abstract要約: 本稿では,ニューラルネットワークの推論効率と探索力と,探索に基づくアルゴリズムの解品質保証とを組み合わせた新しいフレームワークを提案する。 我々のフレームワークはニューラルモデルの選択に非依存であり、ニューラルソルバ単独よりも厳密に優れたソリューションを生成する。
• 参考スコア（独自算出の注目度）: 11.239052168345301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural models have shown promise in solving NP-hard graph combinatorial optimization (CO) problems. Once trained, they offer fast inference and reasonably high-quality solutions for in-distribution testing instances, but they generally fall short in terms of absolute solution quality compared to classical search-based algorithms that are admittedly slower but offer optimality guarantee once search finishes. We propose a novel framework that combines the inference efficiency and exploratory power of neural models with the solution quality guarantee of search-based algorithms. In particular, we use parameterized algorithms (PAs) as the search component. PAs are dedicated to identifying easy instances of generally NP-hard problems, and allow for practically efficient search by exploiting structural simplicity (of the identified easy instances). Under our framework, we use parameterized analysis to identify the structurally hard parts of a CO instance. The neural model handles the hard parts by generating advisory signals based on its data-driven understanding. The PA-based search component then integrates the advisory signals to systematically and efficiently searches through the remaining structurally easy parts. Notably, our framework is agnostic to the choice of neural model and produces strictly better solutions than neural solvers alone. We examine our framework on multiple CO tasks. Empirical results show that it achieves superior solution quality, competitive with that of commercial solvers. Furthermore, by using the neural model only for exploratory advisory signals, our framework exhibits improved out-of-distribution generalization, addressing a key limitation of existing neural CO solvers.
• Abstract（参考訳）: ニューラルモデルはNP-hard graph combinatorial optimization (CO)問題を解く上で有望である。 トレーニングを済ませると、高速な推論と、分散テストインスタンスのための、合理的に高品質なソリューションを提供するが、一般的には、検索が終了すると最適性を保証する古典的な検索ベースアルゴリズムに比べて絶対的なソリューション品質の点で不足する。 本稿では,ニューラルネットワークの推論効率と探索力と,探索に基づくアルゴリズムの解品質保証とを組み合わせた新しいフレームワークを提案する。 特に、探索成分としてパラメータ化アルゴリズム(PA)を用いる。 PAは一般にNPハードな問題の簡単なインスタンスを識別することに専念しており、構造的単純さ(特定容易なインスタンスの)を活用して事実上効率的な検索を可能にしている。 本フレームワークでは,COインスタンスの構造的に硬い部分を特定するためにパラメータ解析を用いる。 ニューラルネットワークは、データ駆動の理解に基づいてアドバイザリ信号を生成することで、ハード部分を処理する。 PAベースの検索コンポーネントは、アドバイザリ信号を統合して、残りの構造的に容易な部分を体系的かつ効率的に検索する。 特に、我々のフレームワークはニューラルモデルの選択に非依存であり、ニューラルソルバ単独よりも厳格に優れたソリューションを生み出している。 複数のCOタスクのフレームワークについて検討する。 実証実験の結果,市販の解法と競合し,優れた解法品質が得られることが示された。 さらに, 探索的助言信号のみにニューラルモデルを用いることで, 既存のニューラルCOソルバの限界に対処し, 分布外一般化を改善した。

関連論文リスト

• Neural Solver Selection for Combinatorial Optimization [23.449310200885893]
  本稿では,特徴抽出,選択モデル,選択戦略を含むニューラルソルバのコーディネートを行うための,最初の汎用フレームワークを提案する。 提案するフレームワークは,インスタンスを効果的に分散し,結果として得られる複合解法により性能が大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-10-13T02:05:41Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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