At-Most-One Constraints in Efficient Representations of Mutex Networks
This work addresses incremental mutex network representation for SAT-based problem solving, but it appears incremental in method.
The paper tackles the problem of efficiently representing mutex networks with At-Most-One constraints to improve Boolean satisfiability solving, showing performance comparisons across different encodings.
The At-Most-One (AMO) constraint is a special case of cardinality constraint that requires at most one variable from a set of Boolean variables to be set to TRUE. AMO is important for modeling problems as Boolean satisfiability (SAT) from domains where decision variables represent spatial or temporal placements of some objects that cannot share the same spatial or temporal slot. The AMO constraint can be used for more efficient representation and problem solving in mutex networks consisting of pair-wise mutual exclusions forbidding pairs of Boolean variable to be simultaneously TRUE. An on-line method for automated detection of cliques for efficient representation of incremental mutex networks where new mutexes arrive using AMOs is presented. A comparison of SAT-based problem solving in mutex networks represented by AMO constraints using various encodings is shown.