Premium
A characterization of irreducible infeasible subsystems in flow networks
Author(s) -
Joormann Imke,
Orlin James B.,
Pfetsch Marc E.
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21686
Subject(s) - characterization (materials science) , cardinality (data modeling) , flow (mathematics) , computation , mathematics , flow network , computer science , discrete mathematics , mathematical optimization , algebra over a field , algorithm , pure mathematics , data mining , nanotechnology , materials science , geometry
Infeasible network flow problems with supplies and demands can be characterized via violated cut‐inequalities of the classical Gale‐Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature by showing a one‐to‐one correspondence between IISs and Gale‐Hoffman‐inequalities in which one side of the cut has to be weakly connected. We also show that a single max‐flow computation allows one to compute an IIS. Moreover, we prove that finding an IIS of minimal cardinality in this special case of flow networks is strongly N P ‐hard. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 121–129 2016
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom