TLDR: A new algorithm, G-CSEA (Graph-based Conflict Set Extraction Algorithm), has been developed to efficiently identify the causes of infeasibility in pseudo-Boolean models, particularly in workforce scheduling. Inspired by SAT solver techniques, G-CSEA constructs an implication graph to trace conflicting constraints, producing significantly smaller conflict sets (94% reduction) and achieving a 40% faster IIS computation time compared to QuickXplain alone. This robust method offers a scalable solution for diagnosing complex scheduling issues.
Workforce scheduling is a complex task involving numerous rules and constraints, such as shift limits, staffing policies, and working hour restrictions. These rules, when combined, can sometimes conflict with each other, leading to what is known as an ‘infeasible model.’ When a scheduling model is infeasible, it means there’s no way to satisfy all the rules simultaneously. Identifying the root causes of such infeasibility is crucial for resolving scheduling problems and making the model workable again.
A common diagnostic method for these issues is to compute Irreducible Infeasible Subsets (IISs). An IIS is a minimal group of constraints that are collectively impossible to satisfy, but if you remove any single constraint from that group, the remaining ones become feasible. Think of it as finding the smallest set of conflicting rules that are causing the entire system to break down.
Many scheduling problems are formulated using pseudo-Boolean constraints, which are linear inequalities involving binary variables (variables that can only be 0 or 1). These constraints are excellent for encoding binary scheduling decisions, like whether an employee is assigned to a shift on a particular day. However, existing methods for finding IISs in these pseudo-Boolean models, such as Additive Deletion and QuickXplain, often require many repeated checks, which can be computationally expensive. Another technique, Dual Ray analysis, works well for continuous linear programs but might fail when the simplified version of the problem is feasible, but the actual pseudo-Boolean model isn’t.
To overcome these limitations, researchers Kanishk Garg, Saranya D., Sanal Kumar, Saurabh Singh, and Anupam Purwar from Sprinklr AI have introduced a new approach called G-CSEA: A Graph-Based Conflict Set Extraction Algorithm. This algorithm is inspired by Conflict-Driven Clause Learning (CDCL), a technique commonly used in SAT (Satisfiability) solvers. The core idea behind G-CSEA is to build an ‘implication graph’ during the process of checking constraints. When a conflict is detected (meaning a rule is violated), the algorithm traces back through this graph to identify all the constraints that contributed to that conflict. This collection of contributing constraints forms a ‘conflict set.’
The G-CSEA algorithm works by iteratively assigning values to variables. It propagates these assignments through the constraints, and if a conflict arises, it analyzes the implication graph to find the responsible constraints. If no conflict is found and the assignment is incomplete, it makes a ‘decision’ by assigning a value to an unassigned variable. When a conflict occurs, the algorithm identifies the latest decision variable involved and can ‘backtrack’ to an earlier decision point to explore alternative assignments. This process continues until either a feasible solution is found, or all possible paths are explored, and a conflict set is returned as the explanation for infeasibility.
While G-CSEA extracts a conflict set, this set can optionally be further minimized using QuickXplain to produce a true Irreducible Infeasible Subset (IIS). The experimental results on workforce scheduling problems have shown significant improvements. G-CSEA, especially when combined with QuickXplain, substantially reduces the number of solver calls needed to find IISs. On average, the conflict sets produced by G-CSEA were about 94% smaller than the original set of constraints, which greatly reduces the work for subsequent minimization.
Furthermore, the method achieved a 40% reduction in IIS computation time compared to using QuickXplain alone. Unlike Dual Ray analysis, G-CSEA is robust and applicable even when the simplified linear programming relaxation of a problem appears feasible, but the actual pseudo-Boolean model is not. This makes it a more reliable tool for purely Boolean models. The algorithm also demonstrates scalability across various model sizes, making it a viable solution for diagnosing infeasibility in complex, constraint-based scheduling systems.
Also Read:
- Advancing Complex Query Answering with Logic-Constrained Vector Symbolic Architecture
- Enhancing AI Decisions: How Expert Mental Models Combat LLM Hallucinations
For more in-depth information, you can read the full research paper here.
