論文の概要: Quantum Speedups for Group Relaxations of Integer Linear Programs

• arxiv url: http://arxiv.org/abs/2602.13494v1
• Date: Fri, 13 Feb 2026 21:58:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 14:17:28.115032
• Title: Quantum Speedups for Group Relaxations of Integer Linear Programs
• Title（参考訳）: 整数線形プログラムの群緩和のための量子スピードアップ
• Authors: Brandon Augustino, Dylan Herman, Guneykan Ozgul, Jacob Watkins, Atithi Acharya, Enrico Fontana, Junhyung Lyle Kim, Shouvanik Chakrabarti,
• Abstract要約: ILPの超クアッドレート量子スピードアップは、多くの制約のあるILPの古典的アルゴリズムが大域的かつ網羅的であるため、入手が困難である。 本稿では,グループ緩和のための競争可能性保存型古典的局所探索アルゴリズムと,それに対応する量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.4310967861393418
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.
• Abstract（参考訳）: Integer Linear Programs (ILP) は、離散最適化問題に対するフレキシブルでユビキタスなモデルである。 ILP を解くことは \textsf{NP-Hard} であるが、実際は非常に重要である。 ILPの超クアッドレート量子スピードアップは、多くの制約のあるILPの古典的アルゴリズムが大域的かつ徹底的であるのに対して、超クアッドレート量子スピードアップを提供する量子フレームワークは、目的と実現可能な集合の局所的構造を利用するため、入手が困難である。 我々は、ゴモリー群緩和のための量子アルゴリズムを介してこの問題に対処する。 ILPの群緩和は、決定変数の積分性を維持しつつ、線形プログラミング(LP)緩和の最適解において正の変数に非負性を持たせることによって得られる。 本稿では,グループ緩和のための競争可能性保存型古典的局所探索アルゴリズムと,それに対応する量子アルゴリズムを提案する。 群緩和がLP非退化に類似しているが強い非退化条件を満たす場合,本手法は元のILPに対する最適解が得られる。 さもなくば、群緩和はILPの最適目的値に束縛され、積分性ギャップを減らして下流の分岐切断を改善することができる。 これらの結果を得るために, グループ緩和のための効率的な構成可能な制約保存ミキサーを導出する。

関連論文リスト

• Hot-Starting Quantum Portfolio Optimization [39.916647837440316]
  滑らかで凸な目的関数による組合せ最適化は、離散平均分散ポートフォリオ最適化のようなアプリケーションで自然に発生する。 我々は、コンパクトなヒルベルト空間を構築することにより、連続最適点近傍の離散解に探索空間を限定する新しいアプローチを導入する。 ソフトウェアソルバとD波アドバンテージ量子アニールの実験により,本手法が最先端技術より優れていることを示す。
  論文  参考訳（メタデータ） (2025-10-13T08:47:43Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound [1.3499500088995464]
  我々は、量子緩和に基づくブランチ・アンド・バウンド(QR-BnB)を開発する。 QR-BnBは、量子緩和をブランチ・アンド・バウンドフレームワークに組み込む方法である。 パウリ作用素の期待値による変数選択戦略は、素数選択よりも収束性が高いことを示す。
  論文  参考訳（メタデータ） (2024-05-02T01:28:52Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)

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

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