Reformulating constraint satisfaction problems to improve scalability

Kenneth M. Bayer, Martin Michalowski, Berthe Y. Choueiry, Craig A. Knoblock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Constraint Programming is a powerful approach for modeling and solving many combinatorial problems, scalability, however, remains an issue in practice. Abstraction and reformulation techniques are often sought to overcome the complexity barrier. In this paper we introduce four reformulation techniques that operate on the various components of a Constraint Satisfaction Problem (CSP) in order to reduce the cost of problem solving and facilitate scalability. Our reformulations modify one or more component of the CSP (i.e., the query, variables domains, constraints) and detect symmetrical solutions to avoid generating them. We describe each of these reformulations in the context of CSPs, then evaluate their performance and effects in on the building identification problem introduced by Michalowski and Knoblock [1].

Original languageEnglish (US)
Title of host publicationAbstraction, Reformulation, and Approximation - 7th International Symposium, SARA 2007 Proceedings
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540735798, 9783540735793
StatePublished - 2007
Event7th International Symposium on Abstraction, Reformulation, and Approximation , SARA 2007 - Whistler, Canada
Duration: Jul 18 2007Jul 21 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4612 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other7th International Symposium on Abstraction, Reformulation, and Approximation , SARA 2007


Dive into the research topics of 'Reformulating constraint satisfaction problems to improve scalability'. Together they form a unique fingerprint.

Cite this