Modelling with Constraints: Theory and Practice
ACP Summer School
Monday 30th June to Friday 4th July 2008
St Andrews, Scotland
http://www-circa.mcs.st-and.ac.uk/cpss2008
Image copyright The University of St Andrews
Image copyright The University of St Andrews
The ACP Summer School 2008 will be held in St. Andrews, Scotland, from June 30th - July 4th 2008. The topic of this year's school will be "Modelling with Constraints: Theory and Practice".
As well as lecture series from world class researchers, participants will use the Minion constraint solver and the Essence modelling language in practical modelling exercises.
The Summer School will take place in the Jack Cole Building (School of Computer Science) on the North Haugh, St Andrews. You can find a map of the University of St Andrews here.
Creating and Extending Efficient Propagating Constraint Solvers
Almost all modern constraint solvers, including Eclipse, ILOG Solver, Gecode and Minion are designed around the principle of propagating constraints. Unlike some early work in constraints where problems were solved by altering the constraints themselves, here the constraints remain fixed and alter the domains of the variables.
There are many details which must be dealt with to design an efficient and extensible constraint solver, many of which are poorly understood and even fewer of which have been written about and studied in depth. In this talk I will show how creating and implementing constraint solvers is simpler than you might expect, once a core of important issues are understood. These talks will show both how to extend existing solvers, and also how writing one from scratch is easier than you might expect.
Talk slides are available as PDF
Thinking Abstractly about Constraint Modelling
When viewed abstractly, many combinatorial problems that we wish to tackle with constraint solving exhibit common features. For example, many problems require us to find combinatorial objects such as sets, relations or functions subject to some side constraints. Typically, these combinatorial objects are not supported directly by constraint solvers, and so a constraint model of the problem must represent them as a constrained collection of more primitive objects. By recognising and developing modelling patterns for representing and constraining combinatorial objects, we can reduce the effort required when modelling a new problem. This talk will teach students how to model problems in a more systematic way by first recognising the combinatorial objects that are required by a problem and then using commonly-occurring patterns to construct the model.
The AllDifferent Constraint: Efficiency Measures"
Talk slides are available as Powerpoint and PDF
Explanations in Constraint Programming
The ability to explain is a classic hallmark of any intelligent system. In these tutorials I will give an overview of explanation generation techniques appropriate for use in constraint programming. Explanations can be useful for pointing out why a set of constraints admits no solutions, but also how to relax a problem so that some solutions are allowed. I will also characterise what makes a good explanation.
Modelling and Solving Two Complex Problems using CP and OR
In this session we will discuss how constraint programming and operations technology can be used to solve some interesting complex problems. As case-studies, we will discuss the problem of generating large domino portraits (a fun problem) and how to solve square packing problems (a complex problem).
Some Classic Papers in Constraint Modeling and Solving
In this session I will lead a discussion group focusing on a small number of classic papers from the constraint programming field. This will be an interactive session. Attendees are expected to have read the recommended papers in advance. (The list of papers will be made available shortly.)
Talk slides are available as PDF
Finding the Solution to Your Problem: How to Go From a High Level Problem Description to the Solutions Using the Minion Constraint Solver
Modelling is arguably the most important aspect of constraint programming (CP), Gene Freuder called modelling the "final frontier" in a guest talk given a few years ago.
In CP a constraint may be specified extensionally by listing its acceptable (satisfying) tuples, or intensionally by giving an expression such as X < Y from which the satisfying tuples can be determined if necessary.
Modelling means to move from a natural language definition of a problem into a CSP instance, if this CSP instance encapsulates all the detail from the problem definition than it is said to provide a model of the problem. It may be possible to find more than one model for a problem, in which case a model is sought which can efficiently be solved, by constraint solving techniques.
This talk will cover how to acquire a constraint model from a natural language problem description. It will go on to explain then how to find a solution to this model using simple techniques such as choosing appropriate variable and value ordering heuristics and simple symmetry breaking constraints. After attending these sessions participants will be able to take a problem and solve it using the Minion constraint solver (http://minion.sourceforge.net/). Participants will be encouraged to practice these new skills in lab sessions.
Limited Discrepancy Search, Revisited
Limited Discrepancy Search (LDS, due to Harvey and Ginsberg) is based on the premise that heuristic decisions are relatively inaccurate near the top of search, and that early mistakes are expensive to correct. The LDS process addresses this by first probing with the heuristic. If this fails LDS then starts again, allowing the search process to go against the heuristic once, i.e. take one discrepancy in all possible ways. If this fails then search starts again, but this time two discrepancies are allowed, and so on to a maximum number. Korf improved LDS (to give ILDS) by eliminating the re-exploration of leaf nodes. However, in ILDS discrepancies are delayed, counter to the intuition behind LDS. Furthermore LDS and ILDS are presented only for problems with binary domains. We present a new version of LDS, one that takes discrepancies in the order prescribed by Harvey and Ginsberg, incorporates Korf's redundancy elimination, whilst dealing with domains of arbitrary size. We then put Harvey and Ginsberg's premise to the test, i.e. are heuristics more accurate at the top of search and is it better to take discrepancies late or take them early? Our experiments suggest that discrepancy order makes little difference, casting doubt on the intuition behind LDS.
Talk slides are available as Powerpoint and PDF
Modelling for Constraint Programming
Constraint programming can be a successful technology for solving practical problems; however, there is abundant evidence that how the problem to be solved is modelled as a Constraint Satisfaction Problem (CSP) can have a dramatic effect on how easy it is to find a solution, or indeed whether it can realistically be solved at all.
A complicating factor is the interaction between the model, the search algorithm and the search heuristics. To simplify matters, in these talks it will be assumed that, having modelled the problem of interest as a CSP, the CSP will be solved using a constraint solver such as ILOG Solver, ECLiPSe, Choco, SICStus Prolog, or the like. The default complete search algorithms provided by these solvers are sufficiently similar that they provide a common context for discussing modelling. Furthermore, they are designed to solve large problems of practical significance, and for such problems, it is worth the effort of developing the best model of the problem that we can find.
It will be assumed that the problem to be solved is well-defined; although eliciting a correct and full problem description can be a significant proportion of the problem-solving effort, it will be assumed here that that step has been done. It will also be assumed that the problem does not involve preferences or uncertainty.
Topics covered will include: choosing a viewpoint (the variables and their domains); expressing the constraints; adding implied constraints; changing viewpoint and combining different viewpoints.
Talk slides are available as Powerpoint: Part1, Part2, Part3, Part4 and PDF: Part1, Part2, Part3, Part4.
Global Constraints
One of the key features of constraint programming is the availability of global constraints. These capture common modelling patterns and come with efficient and effective propagators. From a modelling perspective, global constraints present a challenge to the new user as many different global constraints have been proposed. Recently, several global constraints have been identified (specifically Roots, Range, Regular, and Slide) which can be used to encode many other global constraints. I will show how these global constraint can be used to model a wide range of counting, occurrence and sequencing constraints. If time permits, I will also cover global constraints which can be used to break symmetry statically.
Talk slides are available as Powerpoint: Part 1, Part 2 and PDF: Part 1, Part 2
Using CP When You Don't Know CP
Constraint programming solvers are able to solve an increasing number of problems. However, there are few experts able to model their problem as a constraint network. This lack of experts prevents the spread of Constraint Programming technology in the industry. We will present our first attempts to make constraint programming usable by novices. We will show how the computer can assist the user in representing her problem as a constraint network. We will point out some of the limits of our approach, and we will discuss some of the issues remaining open.
Reformulate Your Network? Why Not Change Your Local Consistency Instead?
Once you have encoded your problem as a constraint network, it is often the case that the solver takes unreasonable amount of time to solve it. In this situation, experts in CP usually reformulate the network by adding implied constraints to increase constraint propagation. We will show that reformulation is not the only way to increase propagation. The CP community has a long history in constraint propagation techniques, and replacing the ubiquitous arc consistency by another level of consistency is sometimes sufficient to obtain the desired amount of propagation.
Talk slides are available as Powerpoint and PDF
The Summer School will start at 9am on Monday 30th June and finish at lunchtime on Friday 4th July.
Participants are advised to arrive on Sunday 29th June.
A full schedule is available here.
There will be financial help to attend the Summer school for those who could not afford to come otherwise. If this money is over subscribed than we will allocate it to the students who have the most to gain from attending this event. If you wish to apply for funding please ask your supervisor to write a letter of recommendation for you and send it to cpss2008@mcs.st-and.ac.uk by Friday the 6th of June when we will confirm funding.
The registration fee for the summer school is 227.50 GBP.
To register to attend the summer school please click here and then select "Book this event". This page can also be used to book accommodation.
Accommodation for the Summer School will be provided in New Hall. You can find some details about the accommodation here.
All rooms are double, en-suite and cost 44.50 GBP per night with a total of 222.50 GBP for 5 nights (Sunday-Thursday).
To arrange accommodation, please use the registration process above.
Some useful information about travelling to St Andrews can be found here