QuickPup: A Heuristic Backtracking Algorithm for the Partner Units Configuration Problem

Abstract

The Partner Units Problem (PUP) constitutes a challenging real-world configuration problem with diverse application domains such as railway safety, security monitoring, electrical engineering, or distributed systems. Although using the latest problem-solving methods including Constraint Programming, SAT Solving, Integer Programming, and Answer Set Programming, current methods fail to generate solutions for midsized real-world problems in acceptable time. This paper presents the QuickPup algorithm based on backtrack search combined with smart variable orderings and restarts. QuickPup outperforms the available methods by orders of magnitude and thus makes it possible to automatically solve problems which couldn’t be solved without human expertise before. Furthermore, the runtimes of QuickPup are typically below one second for real-world problem instances.