論文の概要: An Expansion-Based Approach for Quantified Integer Programming

• arxiv url: http://arxiv.org/abs/2506.04452v1
• Date: Wed, 04 Jun 2025 21:14:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-06 21:53:49.426495
• Title: An Expansion-Based Approach for Quantified Integer Programming
• Title（参考訳）: 量子整数計画法の拡張的アプローチ
• Authors: Michael Hartisch, Leroy Chew,
• Abstract要約: 量子プログラミング(QIP)は、量子ブール公式(QBF)を拡張して複数の領域を橋渡しする QIPは複雑な意思決定シナリオに対処するための汎用的なフレームワークを提供する。 本稿では,CEGARを用いたQIP拡張手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantified Integer Programming (QIP) bridges multiple domains by extending Quantified Boolean Formulas (QBF) to incorporate general integer variables and linear constraints while also generalizing Integer Programming through variable quantification. As a special case of Quantified Constraint Satisfaction Problems (QCSP), QIP provides a versatile framework for addressing complex decision-making scenarios. Additionally, the inclusion of a linear objective function enables QIP to effectively model multistage robust discrete linear optimization problems, making it a powerful tool for tackling uncertainty in optimization. While two primary solution paradigms exist for QBF -- search-based and expansion-based approaches -- only search-based methods have been explored for QIP and QCSP. We introduce an expansion-based approach for QIP using Counterexample-Guided Abstraction Refinement (CEGAR), adapting techniques from QBF. We extend this methodology to tackle multistage robust discrete optimization problems with linear constraints and further embed it in an optimization framework, enhancing its applicability. Our experimental results highlight the advantages of this approach, demonstrating superior performance over existing search-based solvers for QIP in specific instances. Furthermore, the ability to model problems using linear constraints enables notable performance gains over state-of-the-art expansion-based solvers for QBF.
• Abstract（参考訳）: 量子整数プログラミング (Quantified Integer Programming, QIP) は、一般化された整数変数と線形制約を組み込むために、量子論理式 (Quantified Boolean Formulas, QBF) を拡張して複数のドメインをブリッジする。 量的制約満足度問題(QCSP)の特殊な場合として、QIPは複雑な意思決定シナリオに対処するための汎用的なフレームワークを提供する。 さらに、線形目的関数を組み込むことで、QIPは多段階の頑健な離散線形最適化問題を効果的にモデル化することができ、最適化の不確実性に対処するための強力なツールとなる。 QBFには2つの主要なソリューションパラダイム -- 検索ベースと拡張ベースアプローチ -- が存在するが、QIPとQCSPに対してのみ検索ベースの手法が検討されている。 本稿では,QBF からの適応技術である Counterexample-Guided Abstraction Refinement (CEGAR) を用いた QIP の拡張手法を提案する。 我々はこの手法を拡張し、線形制約を伴う多段階頑健な離散最適化問題に取り組み、さらに最適化フレームワークに組み込んで適用性を高める。 実験の結果,本手法の利点を強調し,特定の事例における既存のQIPの探索型解法よりも優れた性能を示した。 さらに、線形制約を用いて問題をモデル化することで、QBFの最先端拡張ベースの解法よりも顕著な性能向上が可能となる。

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化アンサッツのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 確立されたQUBOの定式化と組み合わせた手法をベンチマークし、最適解をサンプリングする確率と解の質を向上した。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
  我々は,任意の2次プログラミング(QP)ソルバに対して,プラグアンドプレイの微分を可能にするモジュール型フレームワークであるdQPを紹介する。 我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。 我々の実装は公開され、15以上の最先端QP解決器をサポートする既存のフレームワークとインターフェースします。
  論文  参考訳（メタデータ） (2024-10-08T20:01:39Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) は、制約近似を避けるための概念的に単純で決定論的アプローチである。 CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
  論文  参考訳（メタデータ） (2023-05-05T19:57:36Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  本稿では,ガンマハイパープライヤを用いた階層的逆問題に対する変分反復交替方式を提案する。 提案した変分推論手法は正確な再構成を行い、意味のある不確実な定量化を提供し、実装が容易である。
  論文  参考訳（メタデータ） (2021-11-26T06:33:29Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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