Analyzing infeasible flow networks (Q2827273)

This book is the doctor's thesis of the author. The aim of this thesis is to expose the theoretical and practical fundamentals of the irreducible infeasible subsystems (IISs) and minimum irreducible infeasible subsystems covers (minIISCs) in networks. The author concentrates on the special case of network flow systems for a simple, directed graph with upper flow bounds \(u\), lower bounds \(l\), and a supply vector \(b\). Thus, with a node arc incidence matrix M, encoding the network graph, the authors considers the infeasible system NEWLINE\[NEWLINE M x = b,\quad l \leq x \leq u.NEWLINE\]NEWLINE The book is organized into five chapters and an appendix. Chapter 1 presents the literature overview and some basics in network theory. One of the author main contributions is the analysis of the characteristics and the computational complexity of IISs, minIISSCs and related problem statements which are presented in Chapter 2. In Chapter 3 are used the observed characteristics to develop a variety of the flow specific heuristics to solve the covering problem. These are then evaluated in Chapter 4 regarding their suitability in practical applications in computational experiments, together with heuristic and optimal approaches known from general linear programs. In Appendix, the author gives (part of) a mixed integer linear programs (MILPs) formulation for stationary gas transport networks. These consist of pipes, compressor station, valves, control valves and (as a modelling help) resistors.NEWLINENEWLINERecommended Readership: researchers in network flow problems.