論文の概要: Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem
- arxiv url: http://arxiv.org/abs/2406.09899v2
- Date: Thu, 20 Jun 2024 01:58:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-22 01:17:00.179782
- Title: Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem
- Title（参考訳）: 二次割当問題を効率的に解くための解認識変換器の学習
- Authors: Zhentao Tan, Yadong Mu,
- Abstract要約: 本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。
QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。
そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
- 参考スコア（独自算出の注目度）: 27.33966993065248
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently various optimization problems, such as Mixed Integer Linear Programming Problems (MILPs), have undergone comprehensive investigation, leveraging the capabilities of machine learning. This work focuses on learning-based solutions for efficiently solving the Quadratic Assignment Problem (QAPs), which stands as a formidable challenge in combinatorial optimization. While many instances of simpler problems admit fully polynomial-time approximate solution (FPTAS), QAP is shown to be strongly NP-hard. Even finding a FPTAS for QAP is difficult, in the sense that the existence of a FPTAS implies $P = NP$. Current research on QAPs suffer from limited scale and computational inefficiency. To attack the aforementioned issues, we here propose the first solution of its kind for QAP in the learn-to-improve category. This work encodes facility and location nodes separately, instead of forming computationally intensive association graphs prevalent in current approaches. This design choice enables scalability to larger problem sizes. Furthermore, a \textbf{S}olution \textbf{AW}are \textbf{T}ransformer (SAWT) architecture integrates the incumbent solution matrix with the attention score to effectively capture higher-order information of the QAPs. Our model's effectiveness is validated through extensive experiments on self-generated QAP instances of varying sizes and the QAPLIB benchmark.
- Abstract（参考訳）: 近年,Mixed Integer Linear Programming Problems (MILPs) などの様々な最適化問題が,機械学習の能力を活用して包括的な調査が行われている。
本研究は,組合せ最適化における重大な課題であるQAP(Quardratic Assignment Problem)を効率的に解くための学習ベースのソリューションに焦点を当てる。
単純な問題の多くは完全多項式時間近似解 (FPTAS) を許容するが、QAPは強いNPハードであることが示されている。
QAP の FPTAS を見つけることは難しいが、FPTAS の存在は$P = NP$ を意味する。
QAPに関する現在の研究は、限られたスケールと計算の非効率さに悩まされている。
上記の課題に対処するため,本研究では,QAPを学習から改善するカテゴリにおいて,QAPの活用に関する第1の解決策を提案する。
この研究は施設ノードと場所ノードを別々にエンコードするが、現在のアプローチで広く使われている計算集約型アソシエーショングラフは形成しない。
この設計選択により、より大きな問題サイズへのスケーラビリティが実現される。
さらに、SAWTアーキテクチャは、既存の解行列と注目スコアを統合して、QAPの高次情報を効果的に取得する。
本モデルの有効性は,様々なサイズの自己生成型QAPインスタンスとQAPLIBベンチマークを用いて検証した。
関連論文リスト
- Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems [15.435730759218776]
擬似非制約二項最適化問題の解を近似する新しい量子インスパイア平均場(QIMF)確率モデルを開発した。
実験により,ポートフォリオ選択,重み付きマックスカット問題,イジングモデルといった大規模問題に対するソリューション評価の大幅な改善が示された。
論文 参考訳（メタデータ） (2024-06-01T01:53:11Z) - Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning [0.22099217573031676]
二次割当問題 (QAP) は、ここ数年研究されてきた実用的な最適化問題である。
QAPを解くための2段階グラフポインタネットワーク(GPN)と呼ばれる深層強化学習モデル。
2段階GPNは、ユークリッド旅行セールスマン問題(TSP)のために提案されたGPNに依存している。
論文 参考訳（メタデータ） (2024-03-31T03:01:56Z) - Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT
instances [0.0]
二次割当問題 (QAP) は、進化的計算最適化の分野における主要な領域の1つである。
本稿では,QAPの相転移について検討し,問題の計算複雑性と充足可能性の劇的な変化と説明できる。
論文 参考訳（メタデータ） (2024-03-05T08:56:30Z) - Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing [0.0]
本稿では、フレキシブルジョブショップスケジューリング問題に対処するため、量子アニーリングに基づく問題解決アルゴリズム(QASA)を提案する。
ベンチマーク問題の実験では、タブ検索、シミュレートされたアニーリング、量子アニーリングを組み合わせたQASAが、古典的解法アルゴリズム(CSA)のソリューション品質を上回っている。
論文 参考訳（メタデータ） (2023-11-16T07:45:57Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
線形制約は、量子アニールで表現できる問題のサイズを減らす。
オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。
D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
論文 参考訳（メタデータ） (2020-12-18T09:48:28Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。