Fugu-MT 論文翻訳(概要): Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

論文の概要: Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

arxiv url: http://arxiv.org/abs/2107.11695v1
Date: Sat, 24 Jul 2021 22:13:42 GMT
ステータス: 処理完了
システム内更新日: 2021-07-28 03:32:38.824044
Title: Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
Title（参考訳）: 高次擬似ブール関数に対する効率的なqubo変換
Authors: Amit Verma, Mark Lewis, Gary Kochenberger
Abstract要約: より高次擬似ブール問題をQUBO形式に変換する方法を持つことは有用である。本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。
参考スコア（独自算出の注目度）: 0.46040036610482665
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.
Abstract（参考訳）: Quadratic Unconstrained Binary Optimization (QUBO) は、幅広い問題をモデリングするための統一フレームワークとして認識されている。 QUBOを解くためにカスタマイズされた商用解決器で問題を解決でき、QUBOは次数2であるため、高次擬似ブール問題をQUBO形式に変換する方法が有用である。標準変換アプローチでは、高次項ごとにペナルティ項によって支えられる追加補助変数が必要である。本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。 QUBOとしてモデル化されたMax 3-SATの大規模実験では、補助変数数の最小化に使用されるサブプロブレムサイズが約100%削減されている。

関連論文リスト

Transforming optimization problems into a QUBO form: A tutorial [45.31975029877049]
2次最適化の実際的な問題には、線形制約によって相互に相互に交わされる変数の多次元配列が含まれることが多い。本論文は,元問題文の3つの主要な変換を同定し,考察する。計算の連続式を提示し、証明し、これらの変換の実装を簡素化する。
論文参考訳（メタデータ） (2024-10-28T14:38:09Z)
Double Momentum Method for Lower-Level Constrained Bilevel Optimization [31.28781889710351]
再帰的仮定を使わずに,非滑らかな暗黙関数定理を応用したLCBOの新しい過次関数を提案する。さらに,2重モーメント法と適応ステップサイズ法に基づいて,テキスト入力ループのシングルタイムスケール反復アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-25T09:05:22Z)
Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
論文参考訳（メタデータ） (2024-05-14T13:28:57Z)
Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations [9.466991829376576]
3SAT-to-QUBO変換の構成において暗黙的に使用されている概念として,Pattern QUBOという名称を導入する。近似的な3SAT-to-QUBO変換は、それでも、場合によっては非常に効果的であることを示す。
論文参考訳（メタデータ） (2023-05-04T08:57:51Z)
Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study [9.466991829376576]
我々はQUBO変換の選択が量子アニールが返す正しい解の数に大きな影響を与えることを示した。また、QUBOインスタンスの異なる2次値の数とその範囲が、解の質に大きな影響を与えることを実証的に示す。
論文参考訳（メタデータ） (2023-05-01T08:40:58Z)
Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文参考訳（メタデータ） (2021-07-26T16:18:43Z)
Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。 BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
論文参考訳（メタデータ） (2021-03-02T16:26:20Z)
Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文参考訳（メタデータ） (2021-01-19T04:24:23Z)
A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
論文参考訳（メタデータ） (2020-09-27T07:15:25Z)
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文参考訳（メタデータ） (2020-08-12T08:52:50Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)

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