Consistency of Constraint Reifications by Reformulation

Abstract: Many combinatorial problems can be formulated via constraints, i.e., relations between variables’ values to be satisfied in order for them to count as a solution for the problem. A lot of these combinatorial relations can be applied to an arbitrary number of arguments, these constraints are called global. Most global constraints (at least 82% in the Global Constraint Catalogue [1]) can be reformulated as a conjunction of total functions together with a constraint which can be directly reified. The reifications are useful in modelling several kinds of combinatorial problems, e.g., when there is a known number of satisfied constraints, but the exact set of satisfied constraints is a priori unknown. In this thesis, we apply different methods in order to determine the consistency level (domain or bounds consistency) of the known reifications, in order to estimate whether the reifications would prune effectively  if they were implemented.