論文の概要: Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems

• arxiv url: http://arxiv.org/abs/2503.10801v1
• Date: Thu, 13 Mar 2025 18:51:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-17 13:05:53.076104
• Title: Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
• Title（参考訳）: 実世界の物流問題のQUBO定式化のための量子および古典的SDP緩和のベンチマーク
• Authors: Birte Ostermann, Taylor Garnowski, Fabian Henze, Vaibhavnath Jha, Asra Dia, Frederik Fiand, David Gross, Wendelin Gross, Julian Nowak, Timo de Wolff,
• Abstract要約: 擬似的非制約二項最適化問題の半定値プログラミング緩和に関する膨大な実験的検討を行った。 オープンな)車両ルーティング問題と(親和性に基づく)スロットリング問題に関する業界ベースの事例のQUBO再構成を検証した。
• 参考スコア（独自算出の注目度）: 0.4636927061010061
• License:
• Abstract: Quadratic unconstrained binary optimization problems (QUBOs) are intensively discussed in the realm of quantum computing and polynomial optimization. We provide a vast experimental study of semidefinite programming (SDP) relaxations of QUBOs using sums of squares methods and on Hamiltonian Updates. We test on QUBO reformulations of industry-based instances of the (open) vehicle routing problem and the (affinity-based) slotting problem -- two common combinatorial optimization problems in logistics. Beyond comparing the performance of various methods and software, our results reaffirm that optimizing over non-generic, real-world instances provides additional challenges. In consequence, this study underscores recent developments towards structure exploitation and specialized solver development for the used methods and simultaneously shows that further research is necessary in this direction both on the classical and the quantum side.
• Abstract（参考訳）: 量子コンピューティングと多項式最適化の領域では、二次非拘束二元最適化問題 (QUBO) が深く議論されている。 本稿では,QUBOの半定値プログラミング(SDP)緩和について,2乗法およびハミルトン更新法を用いて検討した。 本稿では,自動車の(オープンな)ルーティング問題と(親和性に基づく)スロットリング問題(ロジスティクスにおける2つの共通組合せ最適化問題)の産業ベースインスタンスのQUBO再構成を検証した。 各種手法とソフトウェアの性能の比較以外にも,本研究の結果は,非ジェネリックな実世界のインスタンスを最適化することが,さらなる課題をもたらすことを再確認した。 本研究は, 従来手法における構造利用と特殊解法開発に向けた最近の発展を裏付けるとともに, 古典的・量子的両面において, さらなる研究が必要であることを示すものである。

関連論文リスト

• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。 本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。 本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
  論文  参考訳（メタデータ） (2024-07-29T17:13:01Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。 2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
  論文  参考訳（メタデータ） (2024-06-11T19:59:05Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA [4.670374869377859]
  量子アルゴリズムによる最適化問題の解決における中核的なステップは、問題の定式化である。 近年の研究では、多くの問題を自然の多項式非制約最適化形式でより効率的に解けることが示されている。 適切なベンチマーク関数の評価では、PUBOの定式化は一般により良い結果をもたらすが、キュービットは少ない。
  論文  参考訳（メタデータ） (2023-05-05T09:37:48Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。 しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
  論文  参考訳（メタデータ） (2022-10-20T14:54:37Z)
• A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
  本稿では,Isingソルバを用いた混合二項二次プログラムの解法におけるハイブリッドアルゴリズムの形式解析について述べる。 本稿では,ハイブリッド量子古典的切削平面アルゴリズムを用いてこの問題を解決することを提案する。
  論文  参考訳（メタデータ） (2022-07-27T16:47:32Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。 提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。 タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
  論文  参考訳（メタデータ） (2021-06-24T16:39:31Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。 本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
  論文  参考訳（メタデータ） (2021-05-06T02:22:23Z)

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

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