6453
2017
eng
reportzib
0
--
2017-07-17
--
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.
1438-0064
urn:nbn:de:0297-zib-64539
Isabel Beckenbach
Isabel Beckenbach
ZIB-Report
17-36
Mathematical Optimization
Mathematics of Transportation and Logistics
Beckenbach, Isabel
MODAL-RailLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6453/zibreport17_36.pdf