The extensional Constraint
(2019) Doctoral Program of the 25th International Conference on Principles and Practice of Constraint Programming (DPCP19) — Location: Stamford (30.September.2019)
Files
CP2019_doctoral_program3.pdf
Open Access - Adobe PDF
- 301.41 KB
Details
- Authors
- Abstract
- Table constraints and Multi-Valued Decision Diagrams (MDDs) are very useful for modeling combinatorial constrained problems, and thus play an important role in Constraint Programming (CP). During the last decade, many algorithms have been proposed for enforcing the property known as Generalized Arc Consistency (GAC) on such con- straints. A state-of-the-art GAC algorithm called Compact-Table (CT), which has been recently proposed, significantly outperforms all previ- ously proposed algorithms for the extensional constraint. In my thesis, we first extend the CT algorithm in order to deal with basic smart table (i.e., tables with unary expressions such as = v, ∗, 6 = v, ≤ v, ≥ v and ∈ S) and negative tables (i.e., tables containing conflicts instead of solutions). The ideas behind Compact-Table are also used to construct Compact-Diagram (CD), an algorithm handling MDDs and, in general, any ordered layered diagram, with or without decision nodes. Compact-Diagram is also extended to handle basic smart diagrams. Our experimental results show the practical interest of our approaches.
- Affiliations
Citations
Verhaeghe, H. (2019). The extensional Constraint. Doctoral Program of the 25th International Conference on Principles and Practice of Constraint Programming (DPCP19), Stamford. https://hdl.handle.net/2078.5/219401