Fugu-MT 論文翻訳(概要): Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances

論文の概要: Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances

arxiv url: http://arxiv.org/abs/2403.02783v1
Date: Tue, 5 Mar 2024 08:56:30 GMT
ステータス: 処理完了
システム内更新日: 2024-03-06 15:32:35.007202
Title: Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances
Title（参考訳）: 真にハードな二次割り当て問題:QAP-SATインスタンス
Authors: S\'ebastien Verel (LISIC), Sarah Thomson, Omar Rifki (LISIC)
Abstract要約: 二次割当問題 (QAP) は、進化的計算最適化の分野における主要な領域の1つである。本稿では,QAPの相転移について検討し,問題の計算複雑性と充足可能性の劇的な変化と説明できる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Quadratic Assignment Problem (QAP) is one of the major domains in the field of evolutionary computation, and more widely in combinatorial optimization. This paper studies the phase transition of the QAP, which can be described as a dramatic change in the problem's computational complexity and satisfiability, within a narrow range of the problem parameters. To approach this phenomenon, we introduce a new QAP-SAT design of the initial problem based on submodularity to capture its difficulty with new features. This decomposition is studied experimentally using branch-and-bound and tabu search solvers. A phase transition parameter is then proposed. The critical parameter of phase transition satisfaction and that of the solving effort are shown to be highly correlated for tabu search, thus allowing the prediction of difficult instances.
Abstract（参考訳）: 二次割当問題 (QAP) は進化計算の分野における主要な領域の一つであり、より広く組合せ最適化の分野である。本稿では,問題パラメータの狭い範囲において,問題の計算複雑性と満足度が劇的な変化として説明できるqapの相転移について検討する。この現象に対処するために、サブモジュラリティに基づく初期問題のQAP-SAT設計を導入し、新機能の難しさを捉える。この分解は分枝・分枝・分枝探索解法を用いて実験的に検討した。次に相転移パラメータを提案する。位相遷移満足度と解法努力の臨界パラメータは,タブ探索に高い相関関係があることが示され,難解な事例の予測が可能となった。

関連論文リスト

Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
そこで我々は,Dicke状態演算子を用いたGrover Adaptive Search (GAS)を用いて,二次代入問題の探索空間を小さくすることができることを示す。また、GASの位相ゲートをZ軸の回転ゲートに置き換えることで、ペナルティを伴わずに量子回路を簡素化できることを示す。
論文参考訳（メタデータ） (2024-10-16T03:00:37Z)
Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
論文参考訳（メタデータ） (2024-06-14T10:15:03Z)
Solving Quantified Boolean Formulas with Few Existential Variables [19.221715574358207]
QBF問題(Quantified Boolean formula)は、PSPACE完全性のアーキタイプとして一般的に見なされる重要な決定問題である。本稿では,実数量化変数の数という,単純だが見過ごされたパラメータについて考察する。次に、有界節長の共役正規形(CNF)のQBFインスタンスに適用可能な新しいFPTアルゴリズムを開発する。
論文参考訳（メタデータ） (2024-05-10T14:07:29Z)
The Complexity of Optimizing Atomic Congestion [14.845310803203724]
アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。非常に単純なネットワークでも問題は非常に難解なままである。我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
論文参考訳（メタデータ） (2023-12-15T21:31:30Z)
Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。 TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。 TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文参考訳（メタデータ） (2023-10-06T01:40:09Z)
General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
論文参考訳（メタデータ） (2022-04-11T14:11:24Z)
A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
本稿では,ガンマハイパープライヤを用いた階層的逆問題に対する変分反復交替方式を提案する。提案した変分推論手法は正確な再構成を行い、意味のある不確実な定量化を提供し、実装が容易である。
論文参考訳（メタデータ） (2021-11-26T06:33:29Z)
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)
Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文参考訳（メタデータ） (2021-05-05T03:36:00Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)

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