Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141421 | Discrete Optimization | 2015 | 11 Pages |
Abstract
The hypergraph assignment problem (HAP) generalizes the assignment problem from bipartite graphs to bipartite hypergraphs; it is motivated by applications in railway vehicle rotation planning. The HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We show that an algorithmically tractable model providing a strong LP relaxation which implies all clique inequalities can be derived from a suitable extended formulation of polynomial size.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Ralf Borndörfer, Olga Heismann,