Optimising Quantified Expressions in Constraint Models

One of the key difficulties in Constraint Modeling lies in for- mulating an effective constraint model of an input problem for input to a constraint solver: many different models exist for a given prob- lem and it is often difficult - even for experts - to determine the model which is solved most effectively by a constraint solver. In recent years, solver-independent modelling languages (MLs) have become increasingly popular among the CP community, such as OPL, Essence′ or MiniZinc. These languages are very expressive and allow the user to focus on the problem model rather than on the solver input syntax. An important construct in solver-independent MLs are quantifiers, in particular ∀,∃,ﰀ, which are used to scale constraints and expressions in constraints, similarly to for-loops in program code. However, quantified expressions often contain redundancies, in particular in models formu- lated by novices. Such redundancies can have a notable impact on the solving performance of the model, in particular since they often increase with problem size. This paper presents new constraint model optimi- sation techniques concerned with optimising quantified expressions at problem class level. Our experimental results show that quantified expression optimisations can reduce solving time very considerably.