Engineering scalable propagation in constraint programming
(2018)
Files
thesis.pdf
Open Access - Adobe PDF
- 5.47 MB
Details
- Authors
- Supervisors
- Schaus, Pierre
- Abstract
- Combinatorial Optimization is intrinsically hard, including for computers because of the exponential increase of the search space when larger problems are considered. Several technologies have been developed in the previous decades in order to provide computer systems with intelligent reasoning. One of them is Constraint Programming, a declarative paradigm to solve/optimize discrete constrained problems. At the core of this technology lies Propagation, which is responsible for eliminating provable wrong (partial) combinations. This thesis focuses on this part of the Constraint Programming technology. It is well known that 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 the procedures involved in constraint programming propagation, so-called propagators. This is a non-trivial task, since propagation is only a component of the technology and the other parts may influence the solving performances. Specifically, the way search is performed can have a strong repercussion on the performance associated with a given propagator. We therefore introduce a fair manner to evaluate propagators, in the sense that this effect is diminished as much as possible. We also depict an easy technique in order to probe the impact of accelerating a propagator. Despite its simplicity, one can learn if the improvement of a filtering procedure has a chance to be fruitful in practice. On that regard, we give some negative results which are useful for the research community, 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. This constraint can be found in scheduling problems with unary resources in which sequence-dependent transition times between activities are involved. The filtering procedure is able to reason with family-based transition times and optional tasks. We then describe our second propagator, called 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. Both introduced propagators are experimentally evaluated on industrial and academic problems with our evaluation framework. The results show that they generally outperform the state-of-the-art once the size of the problems gets larger. Moreover, they are robust, in the sense that if our approach is slower than the best existing approach on a given problem instance, it is by a small factor.
- Affiliations
Citations
Van Cauwelaert, S. (2018). Engineering scalable propagation in constraint programming. https://hdl.handle.net/2078.5/173274