90C10 Integer programming
Refine
Document Type
- ZIB-Report (2)
Language
- English (2) (remove)
Has Fulltext
- yes (2) (remove)
Is part of the Bibliography
- no (2)
Keywords
- facet (1)
- hyperassignments (1)
- hypergraph (1)
- inequality (1)
- matching (1)
- set packing (1)
- vehicle rotation planning (1)
Institute
- Mathematics of Transportation and Logistics (2) (remove)
The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
Vehicle rotation planning is a fundamental problem in
rail transport. It decides how the railcars, locomotives, and
carriages are operated in order to implement the trips of the
timetable. One important planning requirement is operational
regularity, i.e., using the rolling stock in the same way on every
day of operation. We propose to take regularity into account by
modeling the vehicle rotation planning problem as a minimum cost
hyperassignment problem (HAP). Hyperassignments are generalizations
of assignments from directed graphs to directed hypergraphs.
Finding a minimum cost hyperassignment is
NP-hard.
Most instances arising from regular vehicle rotation planning, however, can
be solved well in practice. We show that, in particular, clique
inequalities strengthen the canonical LP relaxation substantially.