Refinement-driven Transformation for Effective Automated Constraint Modelling

点击翻译按钮获取中文摘要

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.