Skip to main content

The Partner Units Problem − A Constraint Programming Case Study

Conrad Drescher


The Partner Units Problem is a challenging combinatorial search problem that originates in the domain of security and surveillance. Technically it consists of partitioning a bipartite graph under side conditions. In this work we describe how constraint programming technology can be leveraged to tackle the problem. We address problem modelling, symmetry breaking and problem-specific search strategies. We introduce the best search strategy known to date as well as a powerful new implied constraint for pruning the search space. Finally, we present implementations in ECLiPSe Prolog and the MINION constraint solver and compare these to a state-of-the-art dedicated algorithm.

Book Title
Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence‚ ICTAI'12
Athens‚ Greece