Constraint-Based Modelling

Tabling

We added a declarative abstraction to the MiniZinc modelling language so as to allow modellers to recommend subproblems that can be profitably pre-solved (off-line or on-line) into TABLE constraints [DBCFM17].

String Variables and String Constraints

We proposed [SFP13, SFP15, Sco16, SFPS17] the addition of bounded-length string decision variables and string constraints (such as CONCAT, REVERSE, SUBSTRING, etc) to constraint-based modelling languages and CP solvers, reminding also of a simple default way [HFP13b] of implementing them via fixed-length arrays. Experiments show that CP solvers belong to the state of the art for constraint solving over fixed-length and bounded-length string variables.

We extended the MiniZinc solver-technology-independent modelling language accordingly [AFPSST17], integrating it with of our string extension Gecode(S) of the Gecode CP solver and providing as a fallback an interpreter for converting a MiniZinc model with strings into a model relying only on integer variables.

Also see Pierre Flener's invited lecture on string variables in verification at the Master Class on CP and Verification at CPAIOR 2015.

Time-Series Constraints

We made fundamental contributions to the design and efficient CP-style propagation of a very large family of global constraints on time series [ABCDFFPS16], summarised in a PhD dissertation [Fra17]: the missing link in their automatic generation [FFP17], the derivation of their glue constraints [ABCFFPS16], and other improvements [ABDFFPS16].

Indexical Compiler

We extended the indexical language for describing propagators in a solver-independent way and provided an indexical compiler that translates indexical code into propagators for several CP solvers [MFP12] (software).

Relation Variables and Relation Constraints

Relation decision variables, as in our ESRA modelling language (see below), allow an implementation-neutral modelling of many concepts that are usually modelled as matrices of decision variables [FFH+02b].

Symmetry

Symmetry detection and exploitation in models and search is important: see our separate research page on Symmetry.

Modelling Language ESRA

The best account of our constraint-based modelling language ESRA, which is short for Executable Symbolism for Relational Algebra, is in [FPÅ+04]:

• ESRA is high-level. ESRA supports the use of relation decision variables, as originally advocated in [Fle01] and common in software engineering (cf. UML diagrams) and database design (cf. entity-relation-attribute diagrams). A prior design of ESRA supports the use of function decision variables, as originally advocated in [FHK01b]. In the latter publication, we also advocated sequence and permutation decision variables.

• ESRA is solver independent, and even solving-technology independent, as nothing prevents the writing of backends for any constraint processing solver, (constraint-based) local-search solver, or mathematical programming engine, for instance. A prototype compiler of ESRA into SICStus Prolog is described in [Nor06], while a compiler of the functional variant of ESRA into OPL is described in [Wra02, Hni03a].