At the ECAI’94 Workshop on Constraint Processing I gave an invited talk on “The Many Paths to Satisfaction”. The figures for that talk appeared in a chapter of an LNCS volume, along with a short introduction, which began:
When I was asked to give a talk at the ECAI’94 Workshop on Constraint Processing, it occurred to me that the participants could arrive speaking many languages. I am not referring to languages like French and English, or even languages like Lisp and Prolog. Constraint satisfaction problems can be represented in the languages of many different research communities.
I felt that it might be helpful to put together a kind of Rosetta stone for constraint satisfaction, by representing a single simple problem in many different ways.
In fact, I represented the problem (a simple coloring problem) in 15 different ways, as a basic constraint network and as a problem in:
- Predicate Calculus
- Propositional Logic
- Truth Maintenance
- Integer Programming
- Automata Theory
- Graph Theory
- Hill Climbing
- Neural Networks
- Genetic Algorithms
- Relational Algebra
- Constraint Logic Programming
- Constraint Synthesis
- Disjunctive Decomposition
- Conjunctive Decomposition
The last three are alternative constraint satisfaction approaches of my own, but you can see that the list includes a wide variety of approaches, some of which — automata theory? — may surprise you. My point was that “Once a problem is represented as, e.g. a problem in logic or graph theory, then the problem solving tools of that discipline can be brought to bear.” I also, hoped that such a collection might initiate exploration, facilitate comparison, and encourage cross-fertilization.
There are other approaches we might add, at least some of which may not have yet been applied to constraint satisfaction in 1994. Some examples:
- Simulated Annealing
- Parliamentary Optimization Algorithms
- Ant Colony Optimization
- Quantum Computing
- Large Neighborhood Search
- Honey Bee Algorithms
- Neuromorphic Processor
- SAT Modulo Theories (SMT)
I couldn’t quickly find a Slime Mold Solver explicitly for CP, but here’s one for LP. 🙂
Perhaps you can add to this list in the Comments? Perhaps someone would be interested in chiseling new entries into my Rosetta stone?
A number of approaches come under the general heading of “methaheuristics“. Here is a paper Comparing four metaheuristics for solving a constraint satisfaction problem for ship outfitting scheduling. More generally, it would be good if we could identify which approaches worked best for which types of problems (or for which purposes, e.g. some might support better or alternative explanations). The individual papers presenting these approaches presumably offer some insight in this regard, but a survey and/or further study could be useful.
There has been considerable interest in, and success with, “portfolio” approaches that bring together multiple solvers. The above lists might suggest opportunities for “expanded portfolios”.
Gene Freuder 