Identifying Conflicts in Overconstrained Temporal Problems

We describe a strong connection between maximally satisfiable and minimally unsatisfiable subsets of constraint systems. Using this relationship, we develop a two-phase algorithm, employing powerful constraint satisfaction techniques, for the identification of conflicting sets of constraints in infeasible constraint systems. We apply this technique to overconstrained instances of the Disjunctive Temporal Problem (DTP), an expressive form of temporal constraint satisfaction problems. Using randomly-generated benchmarks, we provide experimental results that demonstrate how the algorithm scales with problem size and constraint density.

Authors

• Mark H. Liffiton
• Michael D. Moffitt
• Martha E. Pollack
• Karem A

Keywords

No keywords are indexed for this paper.