Refinement-driven Transformation for Effective Automated Constraint Modelling

Lead Research Organisation: University of St Andrews
Department Name: Computer Science


Constraint programming has been used with great success totackle a wide variety of combinatorial problems in industry andacademia. However, in order to apply constraint programming toa particular domain, the problem must be modelled as aconstraint program. Since constraints provide a rich language, thereare often many possible models, some of which are far more effectivethan others. Therefore, constructing an effective model is a challenging task with very few expert practitioners. This creates a modelling bottleneck, preventing widespread access to the power of constraint technology. Recent work has begun to reduce this bottleneck by casting modelling as the refinement of a model from an abstract specification and automating the refinement process. Effective modelling involves more than just refinement, however. Model transformations, such as breaking symmetries, exploiting dominances, and adding constraints implied by others in the model can greatly increase performance. This proposal addresses a major challenge in the ongoing effort to reduce the modelling bottleneck: to generate effective constraint programs automatically. This goal will be achieved through the formulation of transformation rules that exploit two facets of our own modelling expertise. First, that certain refinements typically produce constraint expressions that can be transformed into a more effective form. Second, that certain constraint expressions, or sets of such expressions, can be transformed in order to trigger a useful refinement that was previously inapplicable. We will embed the transformation rules in the existing automated modelling system, Conjure. This will close the gap between automated and human expert modellers. Hence, the amount of expertise required to exploit powerful constraint solvers will be further diminished, bringing constraint technology closer to the majority.
Description The main goal of this project was successfully achieved: to combine constraint model transformation and refinement to generate more effective constraint programs. Our progress is realised in the (freely available) automated constraint modelling tool, Tailor, which refines an input constraint model in the Essence' language into a format suitable for a particular constraint solver. During this process, Tailor performs a number of transformations that serve to improve the performance of a model when it is finally solved by the target solver. The most successful such transformation we have developed thus far is common subexpression elimination, which detects and exploits the fact that many constraint models (especially those written by non-experts) contain multiple occurrences of the same sub-structure. Eliminating this redundancy can dramatically improve model performance. Common subexpression elimination is further enhanced by selectively rewriting parts of an input model to reveal common subexpressions that were otherwise hidden. The result is an automated constraint modelling system that encodes significant human expertise and can therefore be used even by novices to produce high quality constraint models. NB More recently Tailor has been superseded by a new tool, Savile Row, which can be found at:
Exploitation Route We know that the model chosen of a given problem is crucial to the efficiency with which it can subsequently be solved. This work provides important insights in how we transform and select models. There remains much to learn and our results, embodied in Tailor and Savile Row, provide a platform upon which future research can build.
Sectors Aerospace, Defence and Marine,Agriculture, Food and Drink,Chemicals,Creative Economy,Digital/Communication/Information Technologies (including Software),Energy,Financial Services, and Management Consultancy,Healthcare,Manufacturing, including Industrial Biotechology,Retail,Transport