The Partner Units Configuration Problem: Completing the Picture
This work addresses a benchmark problem for the Logic Programming community, with applications in fields like surveillance and railway safety, but it is incremental as it completes existing complexity analysis.
The paper tackled the computational complexity of the Partner Units Problem (PUP), a hard benchmark with industrial applications, by providing all missing complexity results and introducing QuickPup, a heuristic search algorithm that outperforms state-of-the-art approaches and is used in real-world industrial settings.
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.