Global Constraints
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].
Specification and Synthesis of Global Constraints
Constraint Programming with Systematic Search:
- On-the-fly propagator synthesis for the automated dynamic elimination of auxiliary variables in flattened models [MFP15] (software).
- Propagator design framework, based on dynamic programming, for constraints over sequences [MFP14].
- Indexical compiler: translation of indexical code into propagators for several CP solvers [MFP12] (software).
Constraint-Based Local Search: We designed generic algorithms for incrementally maintaining the violations of a constraint and its decisions variables:
- for a constraint on set decision variables, given by a specification in monadic existential second-order logic [ÅFP07c];
- for a constraint on a sequence of scalar decision variables, given by a specification as a deterministic finite automaton [HFP11, section 8 of HFP13a, section 6 of BCFFP14].
This allows one to evaluate the merits of a model before handcrafting such algorithms for a constraint that is not yet built into the used local search framework.
Reification of Global Constraints
Conventional wisdom has it that many global constraints cannot be easily reified. We have designed a portable method for deriving reified global constraints in a systematic way [BCFP13a]. It is based on the observation that most global constraints can be reformulated as a conjunction of total function constraints together with a constraint that can be easily reified. The method covers 82% of the constraints of the Global Constraint Catalogue
.
AUTOMATON Constraint
The AUTOMATON constraint generalises the REGULAR constraint to finite automata with accumulators and enables the compact encoding of a class of context-sensitive languages. At the start state, the accumulators are initialised. At transitions, the accumulators are updated via arithmetic expressions on constants and other accumulators. At accepting states, the accumulators are linked to a result variable via an arithmetic constraint. It is unknown how to maintain domain consistency efficiently for the AUTOMATON constraint, and the standard approach is to decompose the AUTOMATON constraint into a conjunction of TABLE constraints and arithmetic constraints. Encoding the potential accumulator values into the states so as to enjoy the domain consistency of REGULAR yields an automaton whose size depends on the length of the constrained sequence, leading to combinatorial explosion. Our following results help for special cases:
- Implied constraints can be automatically inferred off-line and added to the decomposition, sometimes leading to domain consistency even in the presence of multiple accumulators [FFP13, FFP15].
- If the result value is unchanged under reversal of the constrained sequence S, then the decomposition can be enriched with implied constraints that link the result on any prefix of S and the result on the corresponding suffix of S. These implied constraints are useful both for constraint programming with systematic search and for constraint-based local search [BCFFP14].
- If there is only one accumulator, which is updated only through increments by constant amounts, then domain consistency can be maintained in polynomial time provided the acceptance constraint is an inequality [BFPVH14].
- For matrix models with AUTOMATON constraints in one direction and COUNT constraints in the other direction, implied constraints can be derived by using the combinatorial technique of double counting [BCFP13b].
CUMULATIVE constraint
Edge finding with cumulative resources: [S10, KFSN11, KFS13, KFSN14].
TREE constraint
We proposed the TREE constraint, which holds if a digraph is partitioned into node-disjoint trees, possibly under side constraints on tree count, node degrees, or precedences and incomparabilities within node subsets [BFL08, BFL05]. This constraint generalises the PATH constraint, as a path is a unary tree. Applications include the construction of a phylogenetic super-tree from given species trees.