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 Beckenbach
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
Place of publication:Cham
Contributing Corporation:Gesellschaft für Operations Research (GOR)
Year of first publication:2018