Like all plans, this is just a plan that is most likely wrong!
Nevertheless, I like to be a man with a plan. Most likely, we will not cover
all of the topics below. We might find that we want to spend more time using
(and abusing) actual constraint programs to solve actual problems. That would be fine.
Introduction: what is a constraint satisfaction problem? How do we
solve it? Who cares? We will use a sample problem, or two, to demonstrate this.
Search Algorithms: we introduce good old fashioned chronological backtracking
(hey, good enough to escape the Minataur!), backward checking algorithms
(maybe not so good) such as backmarking, backjumping, and conflict-directed backjumping.
We then look forwards, with forward checking.
Arc-consistency: what's that then? We introduce arc-consistency, and the
earliest practical algorithm AC3. We then look at support counting algorithms such as AC4.
Then the generic algorithm, AC5, and how we can specialise it. This is the first
step towards a genuine constraint programming toolkit. Finally, we look at AC2001
and ask "Why didn't I think of that?"
The "All Different" Constraint
Feedback on Exercise 1
Heuristics: AR33 sections 5 and 8
- See Peter van Beek's slides (updated by Patrick) on heuristics
- Two papers that may be of interest are
- An empirical study of dynamic variable ordering heuristics for the constraint satisfaction
problem, by Ian Gent, Ewan MacIntyre, Patrick Prosser, Barbara Smith, and Toby Walsh
- Trying harder to fail first, by Barbara Smith and Stuart Grant
- Failing First: an update, by Beck, Prosser, and Wallace
Where are the hard problems?
- Where the Really Hard Problems Are, by Peter Cheeseman, Bob Kanefsky, and
William M. Taylor (pdf)
- Can't get no satisfaction, by Brian Hayes (pdf)
- On the threshold, by Brian Hayes (pdf)
- Constrainedness: constrainedness
- The Constrainedness of Search, by Ian Gent, Patrick Prosser, and Toby Walsh