  The partner units problem (PUP) is an acknowledged hard benchmark problem for
the Logic Programming community with various industrial application fields like
surveillance, electrical engineering, computer networks or railway safety
systems. However, computational complexity remained widely unclear so far. In
this paper we provide all missing complexity results making the PUP better
exploitable for benchmark testing. Furthermore, we present QuickPup, a
heuristic search algorithm for PUP instances which outperforms all
state-of-the-art solving approaches and which is already in use in real world
industrial configuration environments.
