An Optimal Filtering Algorithm for Table Constraints

Select |




Print


Mairy, Jean-Baptiste; Van Hentenryck, Pascal; Deville, Yves


2012-10-08


Conference Material


International Conference on Principles and Practice of Constraint Programming (CP)


Quebec


496-511


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 contain 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). 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.


http://www.cp2012.org/


nicta:5990


Mairy, Jean-Baptiste; Van Hentenryck, Pascal; Deville, Yves. An Optimal Filtering Algorithm for Table Constraints. In: International Conference on Principles and Practice of Constraint Programming (CP); Quebec. 2012-10-08. 496-511. http://hdl.handle.net/102.100.100/99232?index=1



Loading citation data...

Citation counts
(Requires subscription to view)