論文の概要: G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models

• arxiv url: http://arxiv.org/abs/2509.13203v1
• Date: Tue, 16 Sep 2025 16:09:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-17 17:50:53.164197
• Title: G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models
• Title（参考訳）: G-CSEA:疑似ブールモデルにおける不実現性同定のためのグラフベースの競合集合抽出アルゴリズム
• Authors: Kanishk Garg, Saranya D., Sanal Kumar, Saurabh Singh, Anupam Purwar,
• Abstract要約: 一般的な診断手法は、未認識不実現サブセット(IIS)の計算である。 二変数上の不等式関係を持つ擬似ブール制約を用いて定式化されたモデルを考える。 提案手法は制約伝搬中に含意グラフを構築し,コンフリクトを検出すると,両決定枝にまたがるすべての制約をトレースする。
• 参考スコア（独自算出の注目度）: 0.5773629510985792
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Workforce scheduling involves a variety of rule-based constraints-such as shift limits, staffing policies, working hour restrictions, and many similar scheduling rules-which can interact in conflicting ways, leading to infeasible models. Identifying the underlying causes of such infeasibility is critical for resolving scheduling issues and restoring feasibility. A common diagnostic approach is to compute Irreducible Infeasible Subsets (IISs): minimal sets of constraints that are jointly infeasible but become feasible when any one is removed. We consider models formulated using pseudo-Boolean constraints with inequality relations over binary variables, which naturally encode scheduling logic. Existing IIS extraction methods such as Additive Deletion and QuickXplain rely on repeated feasibility checks, often incurring large numbers of solver calls. Dual ray analysis, while effective for LP-based models, may fail when the relaxed problem is feasible but the underlying pseudo-Boolean model is not. To address these limitations, we propose Graph-based Conflict Set Extraction Algorithm (G-CSEA) to extract a conflict set, an approach inspired by Conflict-Driven Clause Learning (CDCL) in SAT solvers. Our method constructs an implication graph during constraint propagation and, upon detecting a conflict, traces all contributing constraints across both decision branches. The resulting conflict set can optionally be minimized using QuickXplain to produce an IIS.
• Abstract（参考訳）: ワークフォーススケジューリングには、シフト制限、スタッフポリシー、労働時間制限など、さまざまなルールベースの制約が含まれます。 このような実現可能性の根本原因を特定することは、スケジューリング問題の解決と実現可能性の回復に不可欠である。 一般的な診断手法は、IIS (Irereducible Infeasible Subsets) を計算することである。 スケジューリングロジックを自然にエンコードするバイナリ変数上の不等式関係を持つ擬似ブール制約を用いて定式化されたモデルを考える。 既存のIIS抽出手法であるAdditive DeletionやQuickXplainは、繰り返し実行可能性チェックに依存しており、多くの場合、多数の解決者コールを発生させる。 2光線解析はLPモデルに有効であるが、緩和された問題が実現可能であるが、基礎となる擬ブールモデルでは失敗する可能性がある。 これらの制約に対処するために、SATソルバにおける競合駆動クロース学習(CDCL)にインスパイアされた競合集合を抽出するグラフベースの衝突集合抽出アルゴリズム(G-CSEA)を提案する。 提案手法は制約伝搬中に含意グラフを構築し,コンフリクトを検出すると,両決定枝にまたがるすべての制約をトレースする。 結果として生じる競合セットは、IISを生成するためにQuickXplainを使用して、任意に最小化することができる。

関連論文リスト

• Efficient Constraint-Aware Flow Matching via Randomized Exploration [10.556484074223258]
  本稿では,フローマッチング (FM) を用いてサンプルを生成する場合の問題点について考察する。 本稿では、制約セットと生成されたサンプルとの距離をペナルティ化する追加用語を用いて、FM目標の簡易な適応を提案する。 提案手法は, 対象分布に適合しながら, 制約満足度の観点から有意な利得が得られることを示す。
  論文  参考訳（メタデータ） (2025-08-18T19:02:02Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  本稿では,ロボット推論と計画における連続的制約満足度問題(CCSP)の解法について紹介する。 対照的に、構成拡散連続制約解法(Diffusion-CCSP)は、CCSPに対する大域的な解を導出する。
  論文  参考訳（メタデータ） (2023-09-02T15:20:36Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。 ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
  論文  参考訳（メタデータ） (2021-02-17T19:55:42Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。 我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。 まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
  論文  参考訳（メタデータ） (2020-08-19T16:04:34Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)

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

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