Propagators for table constraints
(2015)
Files
thesis_mairy_jb.pdf
Open Access - Adobe PDF
- 1.17 MB
Details
- Authors
- Supervisors
- Deville, Yves
- Abstract
- Constraint Programming is devoted to finding solutions to hard combinatorial problems. Such problems usually define exponentially large search spaces. Coping with such search spaces to find solution(s) (or the best solution) is only possible through the use of sophisticated techniques. Several techniques exist and this thesis is focused on one of them: propagation. Propagation aims at removing parts of the search space that provably contain no solution. The constraints are used to locate (and remove) such parts of the search space. The propagation considered in this thesis is that of the Table Constraint. Table constraints are constraints that give explicit access to the list of allowed tuples. Three chapters cover different aspects of propagation for this constraint. In the first one, five different Generalized Arc Consistency (GAC) propagators are proposed for table constraint. Two of them have an optimal time complexity. All the proposed propagators are evaluated on a variety of benchmarks against the state-of-the-art propagators for table constraints. The experimental results show that our propagators are faster than the state of the art when the arity of the tables is between 3 and 4 (inclusive). For binary table constraints, they are outperformed by propagators dedicated only to binary constraints. When the arity is strictly greater than 4, our propagators are competitive with the state of the art. The second chapter covers both GAC propagation and the expressivity of constraint programming. It presents a generalization of table constraint, called Smart Table Constraint, together with its GAC propagator, called smartSTR2. Smart table constraints introduce simple arithmetic expressions inside the allowed tuples. This improves the expressivity and allows an efficient filtering of this new constraint. After presenting the syntax, semantics, and the GAC propagator, that chapter will experimentally compare smartSTR2 with the state-of-the-art GAC propagators on several global constraints. Smart table constraint indeed allow an efficient representation of several well known global constraints. The third chapter is dedicated to a consistency stronger than GAC for table constraints, called Domain $k$-Wise Consistency (DkWC), and a procedure to easily enforce it. This procedure is based on the pre-search computation of a modified CSP such that enforcing GAC on this CSP amounts to enforcing DkWC on the original one. Existing GAC propagators for table constraints can thus be used without any modification to enforce this stronger consistency. Unfortunately, enforcing DkWC is costly. This is also the case for the other consistencies stronger than GAC. We thus also propose two weaker variants of our filtering procedure that are still stronger than GAC but less costly to enforce than full DkWC. These weaker variants, more practical, are compared on a variety of benchmarks to state-of-the-art GAC propagators as well as state-of-the-art propagators for consistencies stronger than GAC. Throughout this thesis, all the proposed algorithms are evaluated on different benchmarks against other alternatives. The results of these evaluations are measurements made on executions of different programs. Those measurements can be tricky to analyze from a statistical viewpoint because they contain missing data (for instance, an algorithm failing to solve an instance within a given time budget) and hypotheses on their distributions are hard to make. In this thesis, we developed a statistical procedure, based on the bootstrap method, to compare algorithms in this context. This procedure is applied to the experimental results presented in this thesis.
- Affiliations
Citations
Mairy, J.-B. (2015). Propagators for table constraints. https://hdl.handle.net/2078.5/191461