論文の概要: Penalty Weights in QUBO Formulations: Permutation Problems

• arxiv url: http://arxiv.org/abs/2206.11040v1
• Date: Mon, 20 Jun 2022 22:00:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-23 16:20:06.073877
• Title: Penalty Weights in QUBO Formulations: Permutation Problems
• Title（参考訳）: QUBO式におけるペナルティ重み:置換問題
• Authors: Mayowa Ayodele
• Abstract要約: 量子コンピュータで動くよう設計された最適化アルゴリズムは 近年 研究の関心を集めています これらの解法の多くは、二項形式と二項形式の問題を最適化することしかできない。 多くの最適化問題があり、自然に置換として表される。 より有望な結果をもたらすペナルティ重みを計算するための新しい静的手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Optimisation algorithms designed to work on quantum computers or other specialised hardware have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. Quadratic Unconstrained Binary Optimisation (QUBO) is therefore a common formulation used by these solvers. There are many combinatorial optimisation problems that are naturally represented as permutations e.g., travelling salesman problem. Encoding permutation problems using binary variables however presents some challenges. Many QUBO solvers are single flip solvers, it is therefore possible to generate solutions that cannot be decoded to a valid permutation. To create bias towards generating feasible solutions, we use penalty weights. The process of setting static penalty weights for various types of problems is not trivial. This is because values that are too small will lead to infeasible solutions being returned by the solver while values that are too large may lead to slower convergence. In this study, we explore some methods of setting penalty weights within the context of QUBO formulations. We propose new static methods of calculating penalty weights which lead to more promising results than existing methods.
• Abstract（参考訳）: 量子コンピュータや他の特殊なハードウェアで動くよう設計された最適化アルゴリズムは近年研究の関心を集めている。 これらの解法の多くは、二項および二次形式にある問題のみを最適化することができる。 したがって、二次非拘束二元最適化(qubo)は、これらの解法で使われる一般的な定式化である。 組み合わさった最適化問題は、例えば旅行セールスマンの問題のように、自然に置換として表される。 しかし、バイナリ変数を用いた置換問題のエンコードにはいくつかの課題がある。 多くのQUBOソルバはシングルフリップソルバであるため、有効な置換に復号できない解を生成することができる。 実現可能なソリューションを生み出すためのバイアスを生み出すには、ペナルティウェイトを使用します。 様々な問題に対して静的なペナルティ重みを設定するプロセスは簡単ではない。 これは、値が小さすぎると解法によって実現不可能な解が返され、大きすぎる値が収束が遅くなる可能性があるためである。 本研究では,QUBO定式化における刑罰重みの設定法について検討した。 本研究では,既存の手法よりも有望な結果をもたらすペナルティ重みを計算する新しい静的手法を提案する。

関連論文リスト

• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。 QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。 論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
  論文  参考訳（メタデータ） (2024-09-09T11:29:46Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
  特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneとD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
  論文  参考訳（メタデータ） (2022-05-26T19:04:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates [14.905085636501438]
  問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。 このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。 qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
  論文  参考訳（メタデータ） (2021-03-19T09:06:12Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)
• 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)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Compressed Quadratization of Higher Order Binary Optimization Problems [5.833700634137687]
  量子および量子に着想を得たアニールの最近のハードウェア進歩は、NPハード最適化問題を解くためにかなりのスピードアップを約束している。 本研究では,イジング空間において,1項の次数還元には2変数の導入が必要であることを証明した。 高次イジング問題に対して、これは結果のQUBO問題のよりコンパクトな表現をもたらす。
  論文  参考訳（メタデータ） (2020-01-02T22:48:50Z)

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

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