TítuloTree decomposition with function filtering
Publication TypeConference Paper
Year of Publication2005
AuthorsMeseguer P, Sánchez M, Larrosa J
EditorBeek P
Conference NameLecture Notes in Computer Science
Volume3709
EditorialSpringer-Verlag
Paginación593 - 606
Resumen

Besides search, complete inference methods can also be used to solve soft constraint problems. Their main drawback is the high spatial complexity. To improve its practical usage, we present an approach to decrease memory consumtion in tree decomposition methods, a class of complete inference algorithms. This approach, called function filtering, allows to detect and remove some tuples that appear to be consistent (with a cost below the upper bound) but that will become inconsistent (with a cost exceeding the upper bound) when extended to other variables. Using this idea, we have developed new algorithms CTEf, MCTEf and IMCTEf, standing for cluster, mini-cluster and iterative mini-cluster tree elimination with function filtering. We demonstrate empirically the benefits of our approach.