ICTEAM - Public Thesis defense - Sascha Van Cauwelaert

Engineering Scalable Propagation in Constraint Programming

Constraint Programming is a declarative paradigm to solve combinatorial problems. This thesis focuses on one of its core components, propagation, which is responsible for eliminating provable wrong combinations. Besides, the amount of data generated and stored is augmenting. Not surprisingly the size of the problems to be solved by optimization also tends to increase. Therefore all our algorithmic design choices are motivated by scalability.

The first part of this work is dedicated to the evaluation of propagators. The way search is performed can have a strong repercussion on the performance associated with a filtering algorithm. We therefore introduce a framework to fairly evaluate them. We also depict an easy technique to probe the impact of accelerating a filtering procedure. One can learn if an improvement has a chance to be fruitful in practice. On that regard, we provide negative results, so that no endeavor is invested on unpromising directions from a practical perspective. Finally, a tool to visualize solver performances is described.

The second part introduces two new scalable propagators that can be used in a broad range of problems. The first one is a unified version of the Unary Resource with Transition Times global constraint. It can be found in scheduling problems with unary resources in which sequence-dependent transition times between activities are involved. We then describe our second propagator, Resource-Cost AllDifferent. It can be used in optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. 

Our experiments illustrate our propagators are robust and generally outperform the state-of-the-art once the size of the problems gets larger.

Membres du jury:

Prof. Pierre Schaus (UCL), supervisor
Prof. Charles Pecheur (UCL), chairperson
Prof. Yves Deville (UCL), secretary
Dr. Michele Lombardi (Unibo, Italie)
Dr. Philippe Laborie (IBM, France)
Prof. Peter Van Roy (UCL)