IIIA CSIC
Published on IIIA CSIC (http://iiia.csic.es)

Home > Two-sided Function Filtering

Two-sided Function Filtering

TitleTwo-sided Function Filtering
Publication TypeConference Paper
Year of Publication2011
AuthorsPujol M [1], Cerquides J [2], Meseguer P [3], Rodríguez-Aguilar JA [4]
Conference Name11th Workshop on Preferences and Soft Constraints
Conference LocationPerugia - Italy
Pagination104-112
Date Published12/09/2011
KeywordsConstraint 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.


Source URL: http://iiia.csic.es/en/node/54648

Links
[1] http://iiia.csic.es/en/staff/marc-pujol-gonzalez
[2] http://iiia.csic.es/en/staff/jes%C3%BAs-cerquides
[3] http://iiia.csic.es/en/staff/pedro-meseguer
[4] http://iiia.csic.es/en/staff/juan-rodr%C3%ADguez-aguilar
[5] http://iiia.csic.es/en/bibliography?f%5Bkeyword%5D=653
[6] http://iiia.csic.es/en/bibliography?f%5Bkeyword%5D=652