The Smart Table Constraint
(2015) 12th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2015) — Location: Barcelona
Files
cpaior2015_smartTable-3.pdf
Open Access - Adobe PDF
- 278.19 KB
Details
- Authors
- Abstract
- Table Constraints are very useful for modeling combinatorial problems in Constraint Programming (CP). They are a universal mechanism for representing constraints, but unfortunately the size of their tables can grow exponentially with their arities. In this paper, we propose to authorize entries in tables to contain simple arithmetic constraints, replacing classical tuples of values by so-called smart tuples. Smart table constraints can thus be viewed as logical combinations of those simple arithmetic constraints. This new form of tuples allows us to encode compactly many constraints, including a dozen of well-known global constraints. We show that, under a very reasonable assumption about the acyclicity of smart tuples, a Generalized Arc Consistency algorithm of low time complexity can be devised. Our experimental results demonstrate that the smart table constraint is a highly promising general purpose tool for CP.
- Affiliations
Citations
Mairy, J.-B., Deville, Y., & Lecoutre, C. (2015). The Smart Table Constraint. Proceedings of 12th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Published. 12th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2015), Barcelona. https://doi.org/10.1007/978-3-319-18008-3_19