6766
2018
eng
309
316
7
Operations Research Proceedings 2017
conferenceobject
Springer
Cham
Gesellschaft für Operations Research (GOR)
0
--
--
--
A Hypergraph Network Simplex Algorithm
We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.
Operations Research Proceedings 2017
yes
urn:nbn:de:0297-zib-64539
2017-11-01
Isabel Beckenbach
Isabel Beckenbach
Natalia Kliewer
Jan Fabian Ehmke
Ralf Borndörfer
Mathematical Optimization
Mathematics of Transportation and Logistics
Beckenbach, Isabel
MODAL-RailLab
MODAL-Gesamt