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.
Links:
[1] http://www.iiia.csic.es/en/individual/marc-pujol-gonzalez
[2] http://www.iiia.csic.es/en/individual/jesus-cerquides
[3] http://www.iiia.csic.es/en/individual/pedro-meseguer
[4] http://www.iiia.csic.es/en/individual/juan-a-rodriguez-aguilar
[5] http://www.iiia.csic.es/en/publications/keyword/WCSP
[6] http://www.iiia.csic.es/en/publications/keyword/Constraint optimization
[7] http://www.iiia.csic.es/en/publications/export/tagged/4409
[8] http://www.iiia.csic.es/en/publications/export/xml/4409
[9] http://www.iiia.csic.es/en/publications/export/bib/4409
[10] http://www.iiia.csic.es/en/project/at
[11] http://www.iiia.csic.es/en/project/eve
[12] http://www.iiia.csic.es/en/project/recedit