論文の概要: Deriving Compact QUBO Models via Multilevel Constraint Transformation
- arxiv url: http://arxiv.org/abs/2404.03610v1
- Date: Thu, 4 Apr 2024 17:34:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 14:02:35.688270
- Title: Deriving Compact QUBO Models via Multilevel Constraint Transformation
- Title（参考訳）: マルチレベル制約変換によるコンパクトQUBOモデルの導出
- Authors: Oksana Pichugina, Yingcong Tan, Christopher Beck,
- Abstract要約: そこで本稿では,QUBOモデルに基づくMLCTS(Multilevel Constraint Transformation Scheme)を提案する。
概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。
MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
- 参考スコア（独自算出の注目度）: 0.8192907805418583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing general-purpose approach that derives QUBO models from binary linear programs (BLP), we propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. We formulate sufficient conditions for the existence of a compact QUBO formulation (i.e., in the original BLP decision space) in terms of constraint levelness and demonstrate the flexibility and applicability of MLCTS on synthetic examples and several well-known combinatorial optimization problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering Problem, the Community Detection Problem, and the Maximum Independence Set Problem. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.
- Abstract（参考訳）: 量子アニーリングとデジタル/CMOSアニーリングのためのカスタマイズハードウェアの進歩により、Quadratic Unconstrained Binary Optimization (QUBO)モデルは最適化の文献で注目を集めている。
従来の2進線形プログラム(BLP)からQUBOモデルを導出する汎用的アプローチにより、我々はより少ない二進変数を持つQUBOモデルを導出する新しいマルチレベル制約変換スキーム(MLCTS)を提案する。
本稿では, コンパクトなQUBO定式化(すなわち, 元のBLP決定空間における)の存在を制約レベルの観点から定式化し, MLCTSの合成例に対する柔軟性と適用性, 最大2-満足性問題, 線形順序問題, コミュニティ検出問題, 最大独立性設定問題など, 良く知られた組合せ最適化問題について述べる。
概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。
MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
関連論文リスト
- 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) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。
CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。
CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
論文 参考訳（メタデータ） (2024-02-05T03:25:04Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
我々はデータからQUBOフォームを導出するのではなく、勾配のバックプロパゲーションを通して学習する。
本稿では,グラフマッチングや2次元点雲のアライメント,3次元回転推定といった多種多様な問題に対する学習QUBOの利点を示す。
論文 参考訳（メタデータ） (2022-10-13T17:59:46Z) - Tightening Discretization-based MILP Models for the Pooling Problem
using Upper Bounds on Bilinear Terms [2.6253445491808307]
線形項による非最適化問題の解法として,離散化に基づく手法が提案されている。
本稿では,離散化に基づくMILPモデルを用いてプール問題の解法を提案する。
論文 参考訳（メタデータ） (2022-07-08T05:28:59Z) - A Variational Inference Approach to Inverse Problems with Gamma
Hyperpriors [60.489902135153415]
本稿では,ガンマハイパープライヤを用いた階層的逆問題に対する変分反復交替方式を提案する。
提案した変分推論手法は正確な再構成を行い、意味のある不確実な定量化を提供し、実装が容易である。
論文 参考訳（メタデータ） (2021-11-26T06:33:29Z) - Machine Learning Framework for Quantum Sampling of Highly-Constrained,
Continuous Optimization Problems [101.18253437732933]
本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。
本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
論文 参考訳（メタデータ） (2021-05-06T02:22:23Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。
通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。
提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
論文 参考訳（メタデータ） (2020-07-26T23:36:22Z) - Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical
and Quantum Computers [3.04585143845864]
本稿では,2次最適化問題に対する現行手法の適用性を高めるために,分解に基づくアプローチを提案する。
我々は、乗算器の交互方向法(ADMM)が、MBOを二項制約のない問題(量子アルゴリズムで解ける)に分割できることを示した。
提案手法の有効性は,Qiskit で実装された量子回路上での VQE と QAOA を用いたシミュレーションにより,いくつかの最適化問題に対して得られた数値結果によって示される。
論文 参考訳（メタデータ） (2020-01-07T14:43:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。