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

These constraints are often modeled using pseudo-Boolean (PB) expressions: linear inequalities over Boolean variables, which directly encode binary scheduling decisions such as assigning an agent to a shift on a given day. When multiple scheduling policies interact--especially across different constraint types--the overall model may become infeasible due to conflicting requirements. In such situations, simply reporting that the model is infeasible offers limited practical insight. Instead, it is crucial to identify Irreducible Infeasible Subsets (IISs): minimal sets of constraints responsible for infeasibility, such that removing any single constraint restores satisfiability. IISs serve as a valuable tool for diagnosing infeasibility, debugging constraint models, and resolving policy-level conflicts in complex scheduling systems. Early work on IIS computation primarily focused on deletion-based and slack-based techniques. Chinneck [3] proposed practical heuristics such as deletion filtering, constraint reordering, constraint grouping, sensitivity analysis filters, and the elastic filter--which augments each constraint with a slack variable and minimizes the total slack to identify likely sources of infeasibility. While effective for continuous linear programs, these methods were not designed for, nor evaluated on, pseudo-Boolean constraint systems involving strictly Boolean variables.