Optimization Methods for the Partner Units Problem
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....
Main Authors: | , , , , , , |
---|---|
Format: | Conference item |
Published: |
Berlin‚ Germany
2011
|
_version_ | 1797105531458945024 |
---|---|
author | Aschinger, M Drescher, C Friedrich, G Gottlob, G Jeavons, P Ryabokon, A Thorstensen, E |
author_facet | Aschinger, M Drescher, C Friedrich, G Gottlob, G Jeavons, P Ryabokon, A Thorstensen, E |
author_sort | Aschinger, M |
collection | OXFORD |
description | 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. |
first_indexed | 2024-03-07T06:48:42Z |
format | Conference item |
id | oxford-uuid:fbbf840c-27fe-4caf-adce-c3152e01f80e |
institution | University of Oxford |
last_indexed | 2024-03-07T06:48:42Z |
publishDate | 2011 |
publisher | Berlin‚ Germany |
record_format | dspace |
spelling | oxford-uuid:fbbf840c-27fe-4caf-adce-c3152e01f80e2022-03-27T13:16:09ZOptimization Methods for the Partner Units ProblemConference itemhttp://purl.org/coar/resource_type/c_5794uuid:fbbf840c-27fe-4caf-adce-c3152e01f80eDepartment of Computer ScienceBerlin‚ Germany2011Aschinger, MDrescher, CFriedrich, GGottlob, GJeavons, PRyabokon, AThorstensen, EIn 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. |
spellingShingle | Aschinger, M Drescher, C Friedrich, G Gottlob, G Jeavons, P Ryabokon, A Thorstensen, E Optimization Methods for the Partner Units Problem |
title | Optimization Methods for the Partner Units Problem |
title_full | Optimization Methods for the Partner Units Problem |
title_fullStr | Optimization Methods for the Partner Units Problem |
title_full_unstemmed | Optimization Methods for the Partner Units Problem |
title_short | Optimization Methods for the Partner Units Problem |
title_sort | optimization methods for the partner units problem |
work_keys_str_mv | AT aschingerm optimizationmethodsforthepartnerunitsproblem AT drescherc optimizationmethodsforthepartnerunitsproblem AT friedrichg optimizationmethodsforthepartnerunitsproblem AT gottlobg optimizationmethodsforthepartnerunitsproblem AT jeavonsp optimizationmethodsforthepartnerunitsproblem AT ryabokona optimizationmethodsforthepartnerunitsproblem AT thorstensene optimizationmethodsforthepartnerunitsproblem |