An optimal filtering algorithm for table constraints
(2012) International Conference on Principles and Practice of Constraint Programming — Location: Québec City, Canada (8.October.2012)
Files
document.pdf
Open Access - Adobe PDF
- 323.42 KB
Details
- Authors
- Abstract
- Filtering algorithms for table constraints are constraint-based, which means that the propagation queue only contains information on the constraints that must be reconsidered. This paper proposes four efficient value-based algorithms for table constraints, meaning that the propagation queue also contains information on the removed values. One of these algorithms (AC5TC-Tr) is proved to have an optimal time complexity of O(r.t + r.d) per table constraint. Experimental results show that, on structured instances, all our algorithms are two or three times faster than the state of the art STR2+ and MDDc algorithms.
- Affiliations
University of Melbourne, Australia Optimization Research Group, NICTA
Citations
Mairy, J.-B., Van Hentenryck, P., & Deville, Y. (2012). An optimal filtering algorithm for table constraints. International Conference on Principles and Practice of Constraint Programming, Québec City, Canada. https://hdl.handle.net/2078.5/219257