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

2 Scopus citations

Abstract

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
Pages64-79
Number of pages16
ISBN (Print)3540735798, 9783540735793
DOIs
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

Other

Other7th International Symposium on Abstraction, Reformulation, and Approximation , SARA 2007
CountryCanada
CityWhistler
Period7/18/077/21/07

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

  • Cite this

    Bayer, K. M., Michalowski, M., Choueiry, B. Y., & Knoblock, C. A. (2007). Reformulating constraint satisfaction problems to improve scalability. In Abstraction, Reformulation, and Approximation - 7th International Symposium, SARA 2007 Proceedings (pp. 64-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4612 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-540-73580-9_8