A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering

• Published in: The Journal of artificial intelligence research 2020-03, Vol.67, p.509-547
• Main Authors: Chabert, Maxime, Solnon, Christine
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Clustering; Computer Science; Consistency; Constraints; Data structures; Data Structures and Algorithms; Multiple criterion
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.1.11870

We introduce the exactCover global constraint dedicated to the exact cover problem, the goal of which is to select subsets such that each element of a given set belongs to exactly one selected subset. This NP-complete problem occurs in many applications, and we more particularly focus on a conceptual clustering application. We introduce three propagation algorithms for exactCover, called Basic, DL, and DL+: Basic ensures the same level of consistency as arc consistency on a classical decomposition of exactCover into binary constraints, without using any specific data structure; DL ensures the same level of consistency as Basic but uses Dancing Links to efficiently maintain the relation between elements and subsets; and DL+ is a stronger propagator which exploits an extra property to filter more values than DL. We also consider the case where the number of selected subsets is constrained to be equal to a given integer variable k, and we show that this may be achieved either by combining exactCover with existing constraints, or by designing a specific propagator that integrates algorithms designed for the NValues constraint. These different propagators are experimentally evaluated on conceptual clustering problems, and they are compared with state-of-the-art declarative approaches. In particular, we show that our global constraint is competitive with recent ILP and CP models for mono-criterion problems, and it has better scale-up properties for multi-criteria problems.