ICTM - Soutenance publique de thèse - M. Jean-Baptiste MAIRY

Constraint Programming (CP) is a paradigm to solve practical problems
described as Constraint Satisfaction Problems (CSPs). A CSP describes
the constraints the solution(s) have to respect, not how to obtain those
solutions. Those constraints can be used to reduce the search space.
Propagation removes parts of the search space that do not contain
solutions, inside so-called propagators. In this thesis, we focus on
propagators for one important constraint: the Table Constraint. Table
constraints list explicitly, in their table, the allowed combinations of values
for their variables. They can thus encode any constraint.

First, five different propagators are proposed for the table constraint to
obtain Generalized Arc Consistency (GAC). Two of them have an optimal
time complexity. Then, we present a new constraint, which is a
generalization of the table constraint, called the Smart Table Constraint.
In the tables of smart table constraints, simple arithmetic constraints are
allowed. This makes the representation of the constraint more efficient
and natural. We also devise an efficient propagator for this constraint to
obtain GAC. Finally, we propose a consistency stronger than GAC for
table constraints. A stronger consistency allows the constraints to further
reduce the search space. The defined consistency is called Domain k-
Wise Consistency (DkWC). We also define a procedure to easily enforce
it, allowing us to reuse existing propagators for GAC without modification.

Throughout this thesis, all the proposed algorithms are evaluated on
different benchmarks against the existing state of the art. We also define
a specialized statistical procedure, based on the bootstrap method, to
compare algorithms. This procedure is used, in addition to traditional
measurements, to evaluate thoroughly the proposed propagators.

Membres du jury :
Prof. Yves DEVILLE (UCL), promoteur
Prof. Peter VAN ROY (UCL), président
Prof. Charles PECHEUR (UCL), secrétaire
Prof. Christophe LECOUTRE (CRIL-CNRS, Université d’Artois, France)
Prof. Pierre SCHAUS (UCL)