論文の概要: Parallel splitting method for large-scale quadratic programs

• arxiv url: http://arxiv.org/abs/2503.16977v1
• Date: Fri, 21 Mar 2025 09:45:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-24 14:55:33.407590
• Title: Parallel splitting method for large-scale quadratic programs
• Title（参考訳）: 大規模二次プログラムの並列分割法
• Authors: Matteo Vandelli, Francesco Ferrari, Daniele Dragoni,
• Abstract要約: SPLITは、大規模二次プログラムを小さなサブプロブレムに分解し、並列に解決するフレームワークである。 SPLITは、高品質なソリューションを提供しながら、計算時間を大幅に削減できることを示す。
• 参考スコア（独自算出の注目度）: 2.520799507359113
• License:
• Abstract: Current algorithms for large-scale industrial optimization problems typically face a trade-off: they either require exponential time to reach optimal solutions, or employ problem-specific heuristics. To overcome these limitations, we introduce SPLIT, a general-purpose quantum-inspired framework for decomposing large-scale quadratic programs into smaller subproblems, which are then solved in parallel. SPLIT accounts for cross-interactions between subproblems, which are usually neglected in other decomposition techniques. The SPLIT framework can integrate generic subproblem solvers, ranging from standard branch-and-bound methods to quantum optimization algorithms. We demonstrate its effectiveness through comparisons with commercial solvers on the MaxCut and Antenna Placement Problems, with up to 20,000 decision variables. Our results show that SPLIT is capable of providing drastic reductions in computational time, while delivering high-quality solutions. In these regards, the proposed method is particularly suited for near real-time applications that require a solution within a strict time frame, or when the problem size exceeds the hardware limitations of dedicated devices, such as current quantum computers.
• Abstract（参考訳）: 大規模産業最適化問題の現在のアルゴリズムはトレードオフに直面しており、最適解に到達するのに指数関数的な時間を必要とするか、問題固有のヒューリスティックを用いるかである。 これらの制限を克服するため、SPLITは大規模二次プログラムを小さなサブプロブレムに分解し、並列に解決する汎用量子インスパイアされたフレームワークである。 SPLITはサブプロブレム間の相互相互作用を説明できるが、他の分解技術では無視される。 SPLITフレームワークは、標準分岐およびバウンド法から量子最適化アルゴリズムまで、汎用サブプロブレムソルバを統合することができる。 最大2万個の決定変数を持つMaxCutおよびアンテナ配置問題の商用解法との比較により,その有効性を示す。 以上の結果から,SPLITは高品質なソリューションを提供しながら,計算時間を大幅に削減できることがわかった。 これらの点において、提案手法は、厳密な時間枠内で解を必要とするほぼリアルタイムなアプリケーションや、現在の量子コンピュータのような専用機器のハードウェア制限を超える場合などに特に適している。

関連論文リスト

• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。 2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
  論文  参考訳（メタデータ） (2024-06-11T19:59:05Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。 私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
  論文  参考訳（メタデータ） (2023-03-06T20:07:05Z)
• 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)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。 この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
  論文  参考訳（メタデータ） (2021-01-19T19:00:40Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Optimizing the Optimizer: Decomposition Techniques for Quantum Annealing [0.0]
  現在の世代の量子コンピュータは、現実世界の問題を解決するには小さすぎる。 本研究では,ベンチマーク問題に対する多種多様なアプローチについて検討する。 その結果,解法の性能は問題グラフの構造に大きく依存していることが示唆された。
  論文  参考訳（メタデータ） (2020-01-16T21:35:16Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。