Heuristics for solving constraint satisfaction problems

by Prof. Erik Aurell (KTH)

Wednesday 11 Feb 2009, 16:00 → 17:00 Europe/Stockholm

RB35 (RB35)

Constraint satisfaction problems (CSPs) are the real-world, and often very large analogs of common leisure-time pursuits such sudoku puzzles. They have been studied intensively in computer science for their theoretical interest, and in industry and applied fields for the direct pay-off from solving them well, in e.g. planning, scheduling, and electronic circuit design (and other fields).

Constraint satisfaction has many connections to combinatorial optimization, i.e. one may talk of "hard constraints" (that need to be satsified) and "soft constraints" (solving them, as well as possible, is then an optimization problem).

While (many) CSPs are provably computationally hard in worst-case, it is a well-known empirical fact that many are also typically easy in practical applications. This observation can be formalized by considering ensembles of random CSPs, and asking whether an instance from such an ensemble can be solved in e.g. linear time, with high probabability, by some incomplete algorithm (heuristic).

I will describe what are to date the most effective local heuristics on the standard benchmarks of random 3-SAT, random 4-SAT, random 5-SAT and random 6-SAT.

I will try to convey two lessons: first, that the best local heuristics (on these problems) are rather different from e.g. simulated annealing, a well known heuristic, and, second, that expected performance can depend quite sensitively on details (parameters) in the heuristics.

As a motivating example, I will use now rather old work with Mats Carlsson and others at SICS to improve the global gene measurement technology of a no longer existing Swedish biotech company. The technology is now long obsolete, but that was in fact my first contact with the field of CSPs.

This is joint work with Mikko Alava, John Ardelius, Petteri Kaski, Supriya Krishnamurthy and Pekka Orponen

Alava M. et al (2008): Circumspect descent prevails in solving random constraint satisfaction problems. Proc. Nat. Acad. Sci. USA: 105, 15253-15257