論文の概要: 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ベンチマークを用いて検証した。
関連論文リスト
- CLAP: Concave Linear APproximation for Quadratic Graph Matching [5.417323487240968]
線形モデルを導入し、グラフマッチングのための新しい近似行列を設計する。
次に、元のQAPを構造制約の凹凸となる線形モデルに変換する。
このモデルはシンクホーン最適輸送アルゴリズムを用いて解くことができる。
論文 参考訳（メタデータ） (2024-10-22T15:28:18Z) - Enhancing Multi-Step Reasoning Abilities of Language Models through Direct Q-Function Optimization [50.485788083202124]
強化学習(Reinforcement Learning, RL)は、大規模言語モデルを人間の好みと整合させ、複雑なタスクを遂行する能力を向上させる上で重要な役割を担っている。
反応生成過程をマルコフ決定プロセス(MDP)として定式化し,ソフトアクター・クリティック(SAC)フレームワークを用いて,言語モデルによって直接パラメータ化されたQ関数を最適化する,直接Q関数最適化(DQO)を提案する。
GSM8KとMATHという2つの数学問題解決データセットの実験結果から、DQOは従来の手法よりも優れており、言語モデルを整合させるための有望なオフライン強化学習手法として確立されている。
論文 参考訳（メタデータ） (2024-10-11T23:29:20Z) - Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
我々は,任意の2次プログラミング(QP)ソルバに対して,プラグアンドプレイの微分を可能にするモジュール型フレームワークであるdQPを紹介する。
我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。
我々の実装は公開され、15以上の最先端QP解決器をサポートする既存のフレームワークとインターフェースします。
論文 参考訳（メタデータ） (2024-10-08T20:01:39Z) - 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) - Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing [0.0]
本稿では、フレキシブルジョブショップスケジューリング問題に対処するため、量子アニーリングに基づく問題解決アルゴリズム(QASA)を提案する。
ベンチマーク問題の実験では、タブ検索、シミュレートされたアニーリング、量子アニーリングを組み合わせたQASAが、古典的解法アルゴリズム(CSA)のソリューション品質を上回っている。
論文 参考訳（メタデータ） (2023-11-16T07:45:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。