|
|
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 2, to demonstrate this,
plus a demo in Oz.
-
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?"
-
A quick intro to claire. We go over the language we will use, and how to install it on
your PC.
-
choco, a constraint programming toolkit. First off we introduce a problem,
with variables and constraints, see propagation working, and allow search to do
its job. We also (try and) install it on a lapTop before your very eyes.
- See our choco page
- See Kevin McDonald's final year report, pages 19 to 29, for his
first cup of choco
- Also look at Kevin's problem kevin.cl
- MAC: maintaining arc-consistency, we put it together. A backtracking search that establishes
arc-consistency after making an instantiation.
-
Jobshop scheduling. (11/02)
-
A first look at representational issues (13/02)
- Three representations for the N-queens here
- The second study: number partitioning here
- Third study: Golomb Ruler here
-
Heuristics: AR33 sections 5 and 8 (18/02)
- variable and value, static and dynamic.
- What are they, and why do they make a difference?
- We look at fail first (renamed "Smallest Domain First" by Barbara Smith and Stuart Grant),
max degree, min bandwidth ordering, Brelaz, and the dual viewpoint heuristic of Geelen.
We also look at max regret.
- See Peter van Beek's slides 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
(ps and pdf)
- Trying harder to fail first, by Barbara Smith and Stuart Grant
(ps and pdf)
-
Search (again) (20/02)
-
A study of encodings of Exercise 1 (25/02)
- A look at assessed exercise 1. How did we do then?
- Patrick in York, giving talk on species trees (3/03)
-
Levels of consistency (4/03)
- GAC, SAC, Inverse consistency, neighbourhood consistency
- See AR33 subsections 7.3, 7.4, and 7.5
- Domain Filtering Consistencies, by R. Debruyne and C. Bessiere
(pdf)
-
SM & CP (5/03)
-
Where are the hard problems? (10/03)
- Phase Transitions: where are the hard problems
- Toby's Oz lecture 5 on phase transitions etc
- Also see AR33 section 6
- Where the Really Hard Problems Are, by Peter Cheeseman, Bob Kanefsky, and
William M. Taylor (pdf)
- Can't get no satisfaction, by Brian Hayes (ps)
- On the threshold, by Brian Hayes
(ps and pdf)
- The Constrainedness of Search, by Ian Gent, Patrick Prosser, and Toby Walsh
(pdf)
-
A Design Problem, and QuickExplain (12/03)
- Kevin's curriculum problem
- A case study of constraint programming for configuration problems, by Kevin McDonald
and Patrick Prosser (pdf)
- Ulrich Junker's QuickExplain.
-
A second look at representation (17/03)
- Revision lecture (19/03)
|
