The hypergraph assignment problem

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.