Department of Information Technology

Constraint-Based Modelling

String Variables

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.

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

Relation Variables

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].
Updated  2017-09-19 16:18:04 by Pierre Flener.