×

Filtering algorithms for the NValue constraint. (English) Zbl 1133.68427

Barták, Roman (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems.; Second international conference, CPAIOR 2005, Prague, Czech Republic, May 31 – June 1, 2005. Refereed proceedings. Berlin: Springer (ISBN 978-3-540-26152-0/pbk). Lecture Notes in Computer Science 3524, 79-93 (2005).
Summary: The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.
For the entire collection see [Zbl 1131.68003].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link