論文の概要: Slack-Free Deep-Unfolded Combinatorial Optimization Solver for Inequality Constraints

• arxiv url: http://arxiv.org/abs/2607.20042v1
• Date: Wed, 22 Jul 2026 11:37:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-23 18:51:38.064874
• Title: Slack-Free Deep-Unfolded Combinatorial Optimization Solver for Inequality Constraints
• Title（参考訳）: 不等式制約に対するSlackフリーのDeep-Unfolded Combinatorial Optimization Solver
• Authors: Ryo Hagiwara, Shunta Arai, Satoshi Takabe,
• Abstract要約: 不均衡なペナル化(UP)はスラック変数を避けるが、元のUP定式化では2つのペナルティ係数をチューニングする必要がある。 不等式制約付きCOPのためのUPとOhzeki法を組み合わせたUPOM法を提案する。
• 参考スコア（独自算出の注目度）: 1.5293427903448018
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum annealing (QA) is used to solve combinatorial optimization problems (COPs). When COPs are implemented on quantum annealers, they are typically encoded as quadratic unconstrained binary optimization (QUBO) problems, but constraint encodings often increase the number of qubits and the embedding overhead. This issue is particularly important for COPs with inequality constraints, where standard slack-variable formulations introduce additional binary variables. Unbalanced penalization (UP) avoids slack variables, but the original UP formulation requires tuning two penalty coefficients and contains a squared residual term that can increase the number of quadratic couplings. In this paper, we propose the unbalanced penalization Ohzeki method (UPOM), which combines UP with the Ohzeki method for inequality-constrained COPs. UPOM replaces the two static penalty coefficients of original UP with an auxiliary-variable update and removes the squared residual term from the Hamiltonian used for sampling. We further propose the deep-unfolded unbalanced penalization Ohzeki method (DU-UPOM), which learns the step-size schedule of the UPOM update from training instances. Numerical experiments on random knapsack problems show that UPOM improves over original UP and that DU-UPOM reaches optimal solutions in fewer iterations than fixed-step UPOM and other baseline. These results demonstrate that the proposed framework reduces the tuning and embedding burdens of UP while making the Ohzeki method trainable for inequality constraints.
• Abstract（参考訳）: 組合せ最適化問題(COP)を解決するために量子アニール(QA)が用いられる。 COPが量子異方体に実装される場合、通常は2次非制約バイナリ最適化(QUBO)問題として符号化されるが、制約符号化はしばしば量子ビットの数と埋め込みオーバーヘッドを増加させる。 この問題は、標準スラック変数の定式化が追加のバイナリ変数を導入する不等式制約を持つCOPにとって特に重要である。 不均衡なペナル化(UP)はスラック変数を避けるが、元のUP定式化では2つのペナルティ係数をチューニングし、二次結合の数を増やすことのできる2乗残差項を含む必要がある。 本稿では,不等式制約のオオゼキ法とオオゼキ法を組み合わせて不等式制約のオオゼキ法(UPOM)を提案する。 UPOMは元のUPの2つの静的なペナルティ係数を補助変数の更新に置き換え、サンプリングに使用されるハミルトニアンから2乗残差項を除去する。 さらに,UPOM更新のステップサイズスケジュールをトレーニングインスタンスから学習するDu-UPOM法(Du-UPOM)を提案する。 ランダムなknapsack問題に関する数値実験により、UPOMは元のUPよりも改善され、DU-UPOMは固定ステップのUPOMや他のベースラインよりも少ないイテレーションで最適解に達することが示された。 これらの結果から,提案手法は,不等式制約に対してオオゼキ法を訓練可能にしつつ,UPのチューニングと埋め込みの負担を軽減することが示唆された。

関連論文リスト

• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。 等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。 完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
  論文  参考訳（メタデータ） (2026-04-20T13:57:49Z)
• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  本研究では,D-ary Optimization (QUDO) を,高次元ヒルベルト空間において決定変数を直接符号化する代替の定式化として検討する。 本研究では,QUDOがトラベリングセールスマン問題,グラフカラー化,ジョブスケジューリング,Max-K-Cutなど,広範なペナルティ構築を必要とせずに,様々な問題クラスにおいて構造的制約を自然に捉えていることを示す。 本研究は、量子最適化のためのスケーラブルで表現力のある表現としてQUDOを強調し、近似比を一貫して改善し、等価回路深さでの計算オーバーヘッドを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2026-02-07T04:37:32Z)
• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  ペナルティに基づく手法は、双レベル最適化(BLO)問題を解くのに人気がある。 それらはしばしば、大きなペナルティ項によって引き起こされる滑らかさの増加に対応するために、低レベル(LL)問題と小さな外ループステップサイズを解決するためにインナーループ反復を必要とする。 この研究は、結合制約(CC)を伴う一般的なBLO問題を考察し、上位変数と下位変数を分離する新しいペナルティ改革を活用する。
  論文  参考訳（メタデータ） (2025-11-20T20:48:14Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  我々は,textbfMixed textbfPrecision textbfQuantizationフレームワークを改良したMPQ-DMv2を提案する。
  論文  参考訳（メタデータ） (2025-07-06T08:16:50Z)
• Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
  変分量子アルゴリズム(VQA)は、通常、ペナルティ法を用いて制約のない問題として再構成されるように制約付き問題を要求する。 一般的なアプローチでは、不等式制約を扱うためにQUBOの定式化においてスラック変数と二次罰則を導入する。 我々は、カスタムペナルティ関数を使って不等式制約を直接エンコードするスラックフリーな定式化について検討する。 これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。
  論文  参考訳（メタデータ） (2025-04-17T03:20:02Z)
• Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling [0.0]
  本稿では,任意の問題をpolynomial Unconstrained Binary Optimization (PUBO)問題に再構成する汎用手法を提案する。 また、擬似非拘束バイナリ最適化(QUBO)問題への総合的な再構成も提供する。 この結果から,PUBOの改定がQUBOよりも優れていることが示唆された。
  論文  参考訳（メタデータ） (2024-11-15T09:23:52Z)
• CBQ: Cross-Block Quantization for Large Language Models [66.82132832702895]
  ポストトレーニング量子化(PTQ)は、超低コストで大規模言語モデル(LLM)を圧縮する上で重要な役割を果たしている。 LLMのためのクロスブロック再構成に基づくPTQ手法CBQを提案する。 CBQはリコンストラクションスキームを使用してクロスブロック依存関係を採用し、エラーの蓄積を最小限に抑えるために複数のブロックにまたがる長距離依存関係を確立する。
  論文  参考訳（メタデータ） (2023-12-13T07:56:27Z)
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage [0.0]
  非バランスなペナル化と呼ばれる新しい手法が、スラック変数の使用を避けるために提案されている。 本研究は、旅行セールスマン問題(TSP)に対するD-Wave Advantage上の実量子ハードウェアを用いた不均衡ペナル化法をテストする。 その結果、不均衡なペナル化法はスラック変数を用いた解よりも優れていた。
  論文  参考訳（メタデータ） (2023-05-30T05:40:50Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)

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

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