Skip to main content

Optimization Methods for the Partner Units Problem

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


In this work we present the Partner Units Problem as a novel challenge for optimization methods. It captures a certain type of configuration problem that frequently occurs in industry. Unfortunately, it can be shown that in the most general case an optimization version of the problem is intractable. We present and evaluate encodings of the problem in the frameworks of answer set programming, propositional satisfiability testing, constraint solving, and integer programming. We also show how to adapt these encodings to a class of problem instances that we have recently shown to be tractable.

Berlin‚ Germany
Book Title
Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011)
Lecture Notes in Computer Science