TitleLower bounds for non-binary constraint optimization problems
Publication TypeConference Paper
Year of Publication2001
AuthorsSánchez M, Larrosa J, Meseguer P
EditorWalsh T
Conference NameLecture notes in computer science

The necessity of non-binary constraint satisfaction algorithms is increasing because many real problems are inherently non-binary. Considering overconstrained problems (and Partial Forward Checking as the solving algorithm), we analyze several lower bounds proposed in the binary case, extending them for the non-binary case. We show that techniques initially developed in the context of reversible DAC can be applied in the general case, to deal with constraints of any arity. We discuss some of the issues raised for non-binary lower bounds, and we study their computational complexity. We provide experimental results of the use of the new lower bounds on overconstrained random problems, including constraints with different weights.