Title | Two-sided Function Filtering |
Publication Type | Conference Paper |
Year of Publication | 2011 |
Authors | Pujol M [1], Cerquides J [2], Meseguer P [3], Rodríguez-Aguilar JA [4] |
Conference Name | 11th Workshop on Preferences and Soft Constraints |
Conference Location | Perugia - Italy |
Pagination | 104-112 |
Date Published | 12/09/2011 |
Keywords | Constraint optimization [5], WCSP [6] |
Abstract | Function filtering enhances dynamic programming methods working on a tree decomposition of the constraint graph. It is based on bounds for tuples: if the lower bound of tuple t is equal to or higher than a suitable upper bound, t can be discarded, decrementing the size of the message to travel in the tree decomposition. We present a new form of lower bound that tightens the lower bound of the original function filtering, so this new version –called two-sided function filtering– is more powerful. We provide experimental evidence of its benefits. |