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.
Author: | Isabel BeckenbachORCiD |
---|---|
Editor: | Natalia Kliewer, Jan Fabian Ehmke, Ralf Borndörfer |
Document Type: | In Proceedings |
Parent Title (English): | Operations Research Proceedings 2017 |
Volume: | Operations Research Proceedings 2017 |
First Page: | 309 |
Last Page: | 316 |
Publisher: | Springer |
Place of publication: | Cham |
Contributing Corporation: | Gesellschaft für Operations Research (GOR) |
Year of first publication: | 2018 |
Page Number: | 7 |
Preprint: | urn:nbn:de:0297-zib-64539 |