TitleTwo-sided Function Filtering
Publication TypeConference Paper
Year of Publication2011
AuthorsPujol M, Cerquides J, Meseguer P, Rodríguez-Aguilar JA
Conference Name11th Workshop on Preferences and Soft Constraints
Conference LocationPerugia - Italy
Date Published12/09/2011
KeywordsConstraint optimization, WCSP

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.