ISBN 9783843924108

978-3-8439-2410-8, Reihe Mathematik

Imke Joormann
Analyzing Infeasible Flow Networks

233 Seiten, Dissertation Technische Universität Darmstadt (2015), Softcover, B5

Zusammenfassung / Abstract

For general linear systems, there are mainly two concepts for infeasibility analysis: Irreducible infeasible subsystems (IISs) and IIS covers (IISCs). In this thesis, we study characteristics and aspects of computational complexity of IISs and IISCs in the special case of infeasible network flow problems with supplies and demands. Infeasible flow networks can be characterized via violated cut-inequalities of the classical Gale-Hoffman theorem. We show a one-to-one correspondence between IISs and those Gale-Hoffman-inequalities in which one side of the cut is weakly connected, as well as strong NP-hardness of finding an IIS of minimal cardinality in flow networks. Along the way, we present some generalizations to gas transportation networks and arbitrary linear systems. Apart from IIS covers, we also investigate the special case of covers which only contain flow bounds (arc covers) and settle their complexity. Moreover, we show inapproximability for minimum arc covers and highlight some polynomially solvable special cases. This leads to the development of two different fixed parameter algorithms. Based on the identified characteristics, we develop a number of heuristics to compute arc covers. These are surveyed regarding their suitability for practical application in computational experiments.