Tackling the Partner Units Configuration Problem

Abstract

The Partner Units Problem is a type of configuration problem, that frequently occurs in industry. Unfortunately, it can be shown that in the general case (the optimization version of) the problem is intractable. In this technical report we identify a tractable class of problem instances that can be solved by a novel algorithm exploiting the notion of a path decomposition. We also present and evaluate encodings for the general version of the problem in the optimization frameworks of answer set programming, propositional satisfiability testing, constraint solving, and integer programming.