On 30 October 1998, Mihaela Sabin and I ran the Constraint Problem Reformulation Workshop in conjunction with the Fourth International Conference on the Principles and Practices of Constraint Programming held in Pisa, Italy. The goals of the workshop were to discuss the nature of constraint problem reformulation and the benefits and difficulties in reformulating constraint problems and to summarize and understand the recent work in this area.
In this paper we describe a reformulation strategy for solving multi-dimensional Constraint Satisfaction Problems (CSPs). This strategy operates by iteratively considering, in isolation, each one of the unidimensional constraints in the problem. It exploits the approximate symmetries identified on the domain values in order to enforce the selected constraint on the simplified problem. This paper uses the game of SET, a combinatorial card game, to motivate and illustrate our strategy. We propose a multi-dimensional constraint model for SET, and describe a basic constraint solver for finding all solutions of an instance of the game. Then, we introduce an algorithm that implements our reformulation strategy, and show that it yields a dramatic reduction of the search effort. Our approach sheds a new light on the dynamic reformulation of CSPs, leading the way to new strategies for effective problem solving. We use the game of SET as a toy problem to illustrate our strategy and explain its operation. We believe that our approach is applicable to more complex domains of scientific and industrial importance, and deserves thorough investigations in the future.
Roughly 30 people attended this workshop. This article summarizes the papers presented at the workshop and highlights some of the questions and issues raised during the discussion. The task of selecting the best representation for solving a problem by means of automatically reformulating the problem is a core challenge in AI. Saul Amarel (1968) outlined the impact of different representations of the missionaries and cannibals problem on the performance of the algorithms used to solve the problem. He also proposed automating the reformulation process and, consequently, the process of selecting representations: The general problem of representation is concerned with the relationship between different ways of formulating a problem to a problem solving system and the efficiency with which the system can be expected to find a solution to the problem.
We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experiments show large differences in favor of our approaches.
The considerable interest in ARA techniques and the great diversity of the researchers involved had led to work on ARA being presented at many different venues. Consequently, there was a need to have a single forum where researchers of different backgrounds and disciplines could discuss their work on ARA. As a result, the Symposium on Abstraction, Reformulation, and Approximation (SARA) was established in 1994 after a series of workshops in 1988, 1990, and 1992. The current SARA, held at Lake Arrowhead, California, USA, on July 7-10, 2009, is the eighth in this series, following symposia in 1994, 1995, 1998, 2000, 2002, 2005, and 2007. Following a SARA tradition, this symposium brought together researchers with different backgrounds and facilitated lively discussions during and after the talks. There were 30 researchers from North and South America, Europe, and Australia. Additionally, SARA attendees were able to mingle and have fruitful discussions with members of the collocated Symposium on Combinatorial Search (SoCS). The collocation of SoCS was particularly useful in that many modern techniques in combinatorial search frequently utilize ARA methods. Finally, in addition to the regular and poster talks, there were three invited talks delivered by Jeff Orkin (Massachusetts Institute of Technology), Michael Genesereth (Stanford University), and Robert Holte (University of Alberta).