The Partner Units Problem − A Constraint Programming Case Study

Abstract

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.