Abstract
The Constraint Satisfaction framework is quite restricted. Nevertheless, it is this restrictiveness that allowed the developments of very useful concepts such as constraint propagation (also know as "consistency enforcement"), through which various tractable subclasses had emerged and by which general purpose algorithms such as backtracking were improved [8,6,7,2]. However, real life problems frequently call for extending the basic model to allow nondeterminism as the representation of preferences among solutions. Such extensions relate the CSP model to known models for combinatorial optimization developed in the Operation Research community as well as to more recent frameworks such as Probabilistic Networks [9]. In this note I argue that extending the CSP model to a richer set of tasks can be done elegantly using a unifying framework which I call "bucket elimination". I believe that this framework will allow hybrids of two fundamental problem solving paradigms: elimination and conditioning, will address computational issues such as time-space tradeoffs, and will allow developing approximation algorithms, all within this general, and therefore, widely applicable framework. In the rest of this note I outline the basic framework.