Publications

Two-sided Function Filtering

Publication Type:

Conference Paper

Authors:

Marc Pujol-Gonzalez; Jesús Cerquides; Pedro Meseguer; Juan A. Rodríguez-Aguilar

Source:

11th Workshop on Preferences and Soft Constraints, Perugia - Italy, p.104-112 (2011)

Keywords:

WCSP; Constraint optimization

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.

Projects: 
AT
EVE
RECEDIT
»