The Rules of Modelling: Automatic Generation of Constraint Programs

Speaker: Alan M. Frisch

19th December 2005 , 2pm , 701 Claremont Tower

Abstract

Many and diverse search 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.