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].

Date

September 22, 2025

Authors

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

Conference

Abstraction, Reformulation, and Approximation: 7th International Symposium, SARA 2007, Whistler, Canada, July 18-21, 2007. Proceedings 7

Pages

64-79

Publisher

Springer Berlin Heidelberg