論文の概要: Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- arxiv url: http://arxiv.org/abs/2110.07239v2
- Date: Mon, 18 Oct 2021 02:33:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-19 11:22:39.178518
- Title: Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- Title(参考訳): 量子アニーリングを用いたミラーリングダブルラウンドロビントーナメントにおける大破れ最小化問題の解法
- Authors: Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
- Abstract要約: 量子異方体は, 実用的な最適化問題の解法として利用できることを示す。
量子異方体の性能を、最も洗練された数学的最適化解法の一つと比較する。
結果: 20チームで問題が発生した場合、QAは0.05秒で正確なソリューションを決定できた。
- 参考スコア(独自算出の注目度): 0.5156484100374059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing (QA) has gained considerable attention because it can be
applied to combinatorial optimization problems, which have numerous
applications in logistics, scheduling, and finance. In recent years, research
on solving practical combinatorial optimization problems using them has
accelerated. However, researchers struggle to find practical combinatorial
optimization problems, for which quantum annealers outperform other
mathematical optimization solvers. Moreover, there are only a few studies that
compare the performance of quantum annealers with one of the most sophisticated
mathematical optimization solvers, such as Gurobi and CPLEX. In our study, we
determine that QA demonstrates better performance than the solvers in the break
minimization problem in a mirrored double round-robin tournament (MDRRT). We
also explain the desirable performance of QA for the sparse interaction between
variables and a problem without constraints. In this process, we demonstrate
that the break minimization problem in an MDRRT can be expressed as a 4-regular
graph. Through computational experiments, we solve this problem using our QA
approach and two-integer programming approaches, which were performed using the
latest quantum annealer D-Wave Advantage, and the sophisticated mathematical
optimization solver, Gurobi, respectively. Further, we compare the quality of
the solutions and the computational time. QA was able to determine the exact
solution in 0.05 seconds for problems with 20 teams, which is a practical size.
In the case of 36 teams, it took 84.8 s for the integer programming method to
reach the objective function value, which was obtained by the quantum annealer
in 0.05 s. These results not only present the break minimization problem in an
MDRRT as an example of applying QA to practical optimization problems, but also
contribute to find problems that can be effectively solved by QA.
- Abstract(参考訳): 量子アニール(QA)は、物流、スケジューリング、ファイナンスに多くの応用がある組合せ最適化問題に適用できるため、注目されている。
近年,それらを用いた組合せ最適化問題を解く研究が加速されている。
しかし、研究者たちは実用的な組合せ最適化問題を見つけるのに苦労しており、量子アニーラーは他の数学的最適化解法よりも優れている。
さらに、量子アニーラーの性能を、gurobiやcplexのような最も洗練された数学的最適化解法の一つと比較する研究はごくわずかである。
そこで本研究では,ミラーリングラウンドロビントーナメント(MDRRT)におけるブレーク最小化問題において,QAが解法よりも優れた性能を示した。
また,変数間の疎相互作用と制約のない問題に対するQAの望ましい性能についても説明する。
本稿では,MDRRTにおけるブレーク最小化問題を4正規グラフとして表現できることを実証する。
計算実験により,最新の量子アニーラーD-WaveAdvantageと高度な数学的最適化解法であるGurobiを用いて,QA法と2整数プログラミング法を用いてこの問題を解く。
さらに,解の質と計算時間を比較する。
QAは20チームでの問題に対して0.05秒で正確なソリューションを決定できた。
36チームの場合、整数プログラミング法が目的関数値に達するのに84.8秒かかり、これは0.05秒の量子アニールによって得られた。
これらの結果は, MDRRTにおけるブレーク最小化問題を, 実用的な最適化問題にQAを適用した例として提示するだけでなく, QAによって効果的に解ける問題を見つけるためにも貢献する。
関連論文リスト
- Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳(メタデータ) (2023-06-14T13:44:35Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
論文 参考訳(メタデータ) (2022-10-20T14:54:37Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳(メタデータ) (2022-05-02T21:30:56Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
車両ルーティング問題(VRP)はNPハード最適化問題である。
この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
論文 参考訳(メタデータ) (2021-12-28T10:20:42Z) - A case study of variational quantum algorithms for a job shop scheduling
problem [0.0]
我々は、IBMの超伝導量子プロセッサ上で動作する4つの変分量子アルゴリズムをジョブショップスケジューリング問題に適用する。
5量子ビットの比較により、最近のフィルタリング変分量子固有解法(F-VQE)はより高速に収束することが示された。
F-VQEは、エラー軽減後処理なしで、ハードウェア上で最大23キュービットの問題を容易に解決する。
論文 参考訳(メタデータ) (2021-09-08T16:05:50Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - 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) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。