Skip to main content

Tackling the Partner Units Configuration Problem

Markus Aschinger‚ Conrad Drescher‚ Gerhard Friedrich‚ Georg Gottlob‚ Peter Jeavons‚ Anna Ryabokon and Evgenij Thorstensen


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.

Computing Laboratory‚ University of Oxford