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.
  • And what is a constraint program?
  • What's it all about? by examples
  • An apes footnote on the crystal maze note828
  • See also AR33 sections 1 and 2
• JChoco, 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 start with simple examples
  • Start 2010: dominos, maths challenge, a bit of maths
  • The Stub
  • The NQueens (CP: "Hello world")
  • A solution to the crystal maze
  • CSP6
  • See our choco page
• 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.
  • bt slides and csp descriptions
  • A demonstration of thrashing
  • cbj slides and M.R.C. van Dongen's Zebra
  • fc slides
  • See also AR33 section 4 and 9
  • 543 CBJ fans can't be wrong
  • Is CBJ a waste of time?
• 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?"
  • ac slides (part 1)
  • ac slides (part 2)
  • how might we represent a variable and a binary constraint?
  • ... arc-consistency, problem, etc.
  • csp6 an interesting test data set, from AR33
  • Bessiere & Regin's paper on ac2001
  • Zhang & Yap's paper on ac2001
  • See also AR33 sections 3 and 7
• Number Partitioning
  • An example of a decision problem
  • An example of an optimisation problem
  • Code and slides on our choco page
• Bin Packing
  • An example of a decision problem
  • An example of an optimisation problem
  • Code and slides on our choco page
• Feedback on Exercise 1
  • Feedback
• Jobshop scheduling.
  • An introduction to constraint programming and jobshop scheduling
  • Sample data sets and code are here
• Where are the hard problems?
  • 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)
  • Constrainedness: constrainedness
  • The Constrainedness of Search, by Ian Gent, Patrick Prosser, and Toby Walsh (pdf)
Heuristics: AR33 sections 5 and 8
• See Peter van Beek's slides (updated by Patrick) on heuristics
• See Toby Walsh's slides (updated by Patrick) on constrainedness
• 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)
  • Failing First: an update, by Beck, Prosser, and Wallace (pdf)
• A second look at representation
  • dual and hidden variable encodings
  • big changes in formulation: independent set
• Specialised Constraints
  • An example using TSP and subtour elimination
  • Sample data sets and code are here
  • Also see our choco page
• Implementing Heuristics in Choco
  • An example using Mad Queens and JSSP
• Search (again)
  • local search and limited discrepancy search
  • Gregg's TSP demo
• Levels of consistency
  • GAC, SAC, Inverse consistency, neighbourhood consistency
  • See AR33 subsections 7.3, 7.4, and 7.5
  • See also Domain Filtering Consistencies
• A Design Problem, and QuickExplain
  • Kevin's curriculum problem
  • A case study of constraint programming for configuration problems, by Kevin McDonald and Patrick Prosser (pdf)
  • Ulrich Junker's QuickExplain.
• Revision
  • last lecture