論文の概要: Towards a Generic Representation of Cominatorial Problems for
Learning-Based Approaches
- arxiv url: http://arxiv.org/abs/2403.06026v1
- Date: Sat, 9 Mar 2024 22:28:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 09:12:49.701579
- Title: Towards a Generic Representation of Cominatorial Problems for
Learning-Based Approaches
- Title（参考訳）: 学習型アプローチの複合的問題表現に向けて
- Authors: L\'eo Boisvert, H\'el\`ene Verhaeghe, Quentin Cappart
- Abstract要約: 近年,問題解決に学習ベースのアプローチを使うことへの関心が高まっている。
この課題は、対象とする問題を学習アルゴリズムと互換性のある構造に符号化することにある。
既存の多くの研究は、しばしばグラフの形で、テキストトグラフニューラルネットワークの利点を活用するために問題固有の表現を提案している。
本稿では,学習に基づくアプローチにおける問題を完全に包括的に表現することを提唱する。
- 参考スコア（独自算出の注目度）: 2.2526069385327316
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In recent years, there has been a growing interest in using learning-based
approaches for solving combinatorial problems, either in an end-to-end manner
or in conjunction with traditional optimization algorithms. In both scenarios,
the challenge lies in encoding the targeted combinatorial problems into a
structure compatible with the learning algorithm. Many existing works have
proposed problem-specific representations, often in the form of a graph, to
leverage the advantages of \textit{graph neural networks}. However, these
approaches lack generality, as the representation cannot be easily transferred
from one combinatorial problem to another one. While some attempts have been
made to bridge this gap, they still offer a partial generality only. In
response to this challenge, this paper advocates for progress toward a fully
generic representation of combinatorial problems for learning-based approaches.
The approach we propose involves constructing a graph by breaking down any
constraint of a combinatorial problem into an abstract syntax tree and
expressing relationships (e.g., a variable involved in a constraint) through
the edges. Furthermore, we introduce a graph neural network architecture
capable of efficiently learning from this representation. The tool provided
operates on combinatorial problems expressed in the XCSP3 format, handling all
the constraints available in the 2023 mini-track competition. Experimental
results on four combinatorial problems demonstrate that our architecture
achieves performance comparable to dedicated architectures while maintaining
generality. Our code and trained models are publicly available at
\url{https://github.com/corail-research/learning-generic-csp}.
- Abstract（参考訳）: 近年,従来の最適化アルゴリズムと組み合わさって,組み合わさった問題を解決するための学習ベースのアプローチへの関心が高まっている。
どちらのシナリオでも、ターゲットの組合せ問題を学習アルゴリズムと互換性のある構造に符号化することが課題である。
既存の多くの著作は、しばしばグラフの形で問題固有の表現を提案し、 \textit{graph neural networks} の利点を生かしている。
しかし、これらのアプローチは、表現が一つの組合せ問題から別の問題へ容易に転送できないため、一般性に欠ける。
このギャップを埋める試みはいくつか行われているが、部分的な一般化のみを提供する。
この課題に対して,本論文は,学習ベースアプローチにおける組合せ問題を完全に一般化した表現に向けての進歩を提唱する。
提案するアプローチは、組合せ問題の制約を抽象構文木に分解し、エッジを通して関係(例えば制約に関わる変数)を表現することによってグラフを構築することである。
さらに,この表現から効率的に学習できるグラフニューラルネットワークアーキテクチャを導入する。
このツールはXCSP3フォーマットで表現された組合せ問題で動作し、2023年のミニトラックコンペティションで利用可能なすべての制約を処理する。
4つの組合せ問題に対する実験結果から,本アーキテクチャは汎用性を維持しつつ,専用アーキテクチャに匹敵する性能を実現することが示された。
私たちのコードとトレーニングされたモデルは、 \url{https://github.com/corail-research/learning-generic-csp}で公開されている。
関連論文リスト
- LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。
本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文 参考訳（メタデータ） (2024-07-18T22:05:21Z) - GOAL: A Generalist Combinatorial Optimization Agent Learning [0.05461938536945722]
GOALは複数のハード最適化問題(COP)を効率的に解くことができるモデルである
ゴールは1つのバックボーンと、入力および出力処理用の軽量な問題固有のアダプタで構成されている。
GOALは,幅広いCOPを解く最初のマルチタスクモデルでありながら,特定のベースラインよりもわずかに劣っている。
論文 参考訳（メタデータ） (2024-06-21T11:55:20Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - A Unified Analysis of Dynamic Interactive Learning [5.474944738795308]
Emamjomeh-Zadeh氏らによる以前の研究は、非静的なユーザの好みをモデル化する手段として、インタラクティブな学習のダイナミクスを導入しました。
私たちは、[Emamjomeh-Zadeh et al., 2020]で分析されたモデルの両方をキャプチャするフレームワークを提供します。
また,学習者が各ラウンドのフィードバックに従う,効率的なアルゴリズムについても検討する。
論文 参考訳（メタデータ） (2022-04-14T16:03:37Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - CombOptNet: Fit the Right NP-Hard Problem by Learning Integer
Programming Constraints [20.659237363210774]
我々は、コスト項と制約の両方を学習できる層として、整数型プログラミングソルバをニューラルネットワークアーキテクチャに統合することを目指している。
結果として得られたエンドツーエンドのトレーニング可能なアーキテクチャは、生データから特徴を共同で抽出し、最先端の整数プログラミング解法で適切な(学習した)問題を解く。
論文 参考訳（メタデータ） (2021-05-05T21:52:53Z) - Neural Learning of One-of-Many Solutions for Combinatorial Problems in
Structured Output Spaces [20.101005623256626]
複数のソリューションの存在に消極的であることは、トレーニング能力を著しく損なう可能性がある、と私たちは主張する。
本稿では、既存の予測ネットワークをRL問題に適用し、解乗法を扱う汎用学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-08-27T08:37:01Z) - Multi-view Graph Learning by Joint Modeling of Consistency and
Inconsistency [65.76554214664101]
グラフ学習は、複数のビューから統一的で堅牢なグラフを学ぶ能力を備えた、マルチビュークラスタリングのための有望なテクニックとして登場した。
本稿では,統合目的関数における多視点一貫性と多視点不整合を同時にモデル化する,新しい多視点グラフ学習フレームワークを提案する。
12のマルチビューデータセットに対する実験は、提案手法の堅牢性と効率性を実証した。
論文 参考訳（メタデータ） (2020-08-24T06:11:29Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。