Joint talk with Bath University: The Rules of Modelling Automatic Generation of Constraint Programs

Alan Frisch

(York)

Many and diverse combinatorial problems have been solved with great success using constraint programming. However, to employ constraint programming technology to solve a problem, the problem first must be characterised, or modelled, by a set of constraints that its solutions must satisfy. Generating a correct model can be difficult; generating one that is easier to solve than its alternatives is even more difficult, often requiring considerable expertise. This so-called "modelling bottleneck" has inhibited the wider use of constraint programming technology. This talk describes CONJURE, a rule-based system that automatically generates constraint programs by refining an abstract problem specification. Since the high-level specification language is significantly closer than a constraint program to the way in which problems are commonly conceived, the modelling bottleneck is substantially reduced. A particular focus of this talk is showing why the refinement rules must be recursive, why this is difficult to achieve and how we ultimately solved solved this problem. This talk assumes no background in constraint programming.
Thursday 22nd April 2010, 14:00
Far-134 (Video Conferencing Room)
Department of Computer Science