論文の概要: On Dedicated CDCL Strategies for PB Solvers

• arxiv url: http://arxiv.org/abs/2109.01013v1
• Date: Thu, 2 Sep 2021 15:22:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-03 13:55:07.458665
• Title: On Dedicated CDCL Strategies for PB Solvers
• Title（参考訳）: PBソルバーの専用CDCL戦略について
• Authors: Daniel Le Berre and Romain Wallon
• Abstract要約: PB制約の特異性を考慮し,CDCL戦略を適応させるさまざまな方法を提案し,評価する。 我々の実験は、これらの専用戦略が、時としてこれらの解法の性能を改善できることを示している。
• 参考スコア（独自算出の注目度）: 6.716102421801302
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current implementations of pseudo-Boolean (PB) solvers working on native PB constraints are based on the CDCL architecture which empowers highly efficient modern SAT solvers. In particular, such PB solvers not only implement a (cutting-planes-based) conflict analysis procedure, but also complementary strategies for components that are crucial for the efficiency of CDCL, namely branching heuristics, learned constraint deletion and restarts. However, these strategies are mostly reused by PB solvers without considering the particular form of the PB constraints they deal with. In this paper, we present and evaluate different ways of adapting CDCL strategies to take the specificities of PB constraints into account while preserving the behavior they have in the clausal setting. We implemented these strategies in two different solvers, namely Sat4j (for which we consider three configurations) and RoundingSat. Our experiments show that these dedicated strategies allow to improve, sometimes significantly, the performance of these solvers, both on decision and optimization problems.
• Abstract（参考訳）: ネイティブPB制約に係わる疑似ブール解法(PB)の現在の実装は、高効率な現代的なSAT解法を実現するCDCLアーキテクチャに基づいている。 特に、このようなpbソルバは(カットプレーンに基づく)競合解析手順を実装するだけでなく、cdclの効率に不可欠なコンポーネント、すなわち分岐ヒューリスティック、学習された制約削除と再起動のための補完的な戦略も実装している。 しかし、これらの戦略はPBソルバが扱うPB制約の特定の形態を考慮せずに再利用することが多い。 本稿では,CDCL戦略を適応させ,PB制約の特異性を考慮し,その動作を包括的に保ちながら,CDCL戦略を適応させる方法について検討する。 これらの戦略をsat4j (3つの構成を考える) と roundingsat という2つの異なる解法で実装した。 我々の実験は、これらの専用戦略が、決定問題と最適化問題の両方において、これらの解法の性能を改善できることを示している。

関連論文リスト

• Hierarchical Upper Confidence Bounds for Constrained Online Learning [4.8951183832371]
  階層的制約付き帯域幅(HCB)フレームワークを導入し、コンテキスト的帯域幅問題を拡張して階層的決定構造とマルチレベル制約を組み込む。 我々の理論的解析はHC-UCBのサブ線形後悔境界を確立し、すべての階層レベルでの制約満足度を高い確率で保証する。
  論文  参考訳（メタデータ） (2024-10-22T17:41:14Z)
• Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought [61.588465852846646]
  大型言語モデル(LLM)の性能向上のための有望なアプローチとして、Chain-of-Thought(CoT)推論が登場した。 本稿では,これらの課題に対処するための新しい推論境界フレームワーク(RBF)を提案する。
  論文  参考訳（メタデータ） (2024-10-08T05:26:28Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Recursively-Constrained Partially Observable Markov Decision Processes [13.8724466775267]
  C-POMDPは連続的な決定ステップに対して最適なサブ構造特性に反することを示す。 C-POMDPのオンライン再計画は、この違反による不整合のため、しばしば効果がない。 本稿では,C-POMDPに履歴に依存したコスト制約を課す再帰的制約付きPOMDPを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:25:07Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Revisiting GANs by Best-Response Constraint: Perspective, Methodology, and Application [49.66088514485446]
  ベストレスポンス制約(Best-Response Constraint、BRC)は、ジェネレータのディスクリミネータへの依存性を明示的に定式化する一般的な学習フレームワークである。 モチベーションや定式化の相違があっても, フレキシブルBRC法により, 様々なGANが一様に改善できることが示される。
  論文  参考訳（メタデータ） (2022-05-20T12:42:41Z)
• Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
  勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。 機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。 上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
  論文  参考訳（メタデータ） (2021-10-11T03:13:39Z)
• On Improving the Backjump Level in PB Solvers [2.741266294612776]
  PB制約が存在する場合,SATソルバにおいて最も高いバックジャンプを行う保証がないことを示す。 コンフリクト分析で同定されたバックジャンプレベルを改善するために,様々なアプローチを導入,評価する。 実験の結果, PBソルバでは準最適バックジャンプがよく見られるが, その影響は明らかでない。
  論文  参考訳（メタデータ） (2021-07-27T21:23:03Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)

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

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