A Decomposition Technique for CSPs Using Maximal Independent Sets and Its Integration with Local Search

Joel Gompert and Berthe Y. Choueiry, University of Nebraska-Lincoln

We introduce IndSet, a technique for decomposing a Constraint Satisfaction Problem (CSP) by identifying a maximal independent set in the constraint graph of the CSP. We argue that this technique reduces the complexity of solving the CSP exponentially by the size of the maximal independent set, and yields compact and robust solutions. We discuss how to integrate this decomposition technique with local search, and evaluate SLS/IndSet, which combines IndSet with a stochastic local search. Finally, we discuss the benefit of identifying dangling components of the decomposed constraint graph, and evaluate SLS/IndSet+Dangles, a strategy that exploits this structural improvement.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.