G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models

• URL: http://arxiv.org/abs/2509.13203v1
• Date: Tue, 16 Sep 2025 16:09:30 GMT
• Title: G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models
• Authors: Kanishk Garg, Saranya D., Sanal Kumar, Saurabh Singh, Anupam Purwar,
• Abstract summary: A common diagnostic approach is to compute Irreducible Infeasible Subsets (IIS)<n>We consider models formulated using pseudo-Boolean constraints with inequality relations over binary variables.<n>Our method constructs an implication graph during constraint propagation and, upon detecting a conflict, traces all contributing constraints across both decision branches.
• Score: 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.

Related papers

• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• CORGI: Efficient Pattern Matching With Quadratic Guarantees [0.0]
  We show how an algorithm called CORGI can solve problems in tight time constraints for AI-based systems.<n> CORGI finds single satisficing matches, and the ability stream to memory without committing entire conflict sets to memory.
  arXiv  Detail & Related papers  (2025-11-17T21:49:39Z)
• Efficient Constraint-Aware Flow Matching via Randomized Exploration [10.556484074223258]
  We consider the problem of generating samples via Flow Matching (FM) with an additional requirement that the generated samples must satisfy given constraints.<n>We propose a simple adaptation of the FM objective with an additional term that penalizes the distance between the constraint set and the generated samples.<n>We numerically show that the proposed approaches achieve significant gains in terms of constraint satisfaction while matching the target distributions.
  arXiv  Detail & Related papers  (2025-08-18T19:02:02Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  We introduce a new model-oriented approach for Answer Set Programming that lifts the Symmetry Breaking Constraints into a set of interpretable first-order constraints. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs.
  arXiv  Detail & Related papers  (2021-12-22T11:27:48Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. We propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution.
  arXiv  Detail & Related papers  (2020-05-29T00:13:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.