Optimization Online


A Characterization of Irreducible Infeasible Subsystems in Flow Networks

Imke Joormann (i.joormann***at***tu-braunschweig.de)
James B. Orlin (jorlin***at***mit.edu)
Marc E. Pfetsch (pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: 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 give a polynomial-time algorithm that computes some IIS using a single max-flow computation and show strong NP-hardness of finding an IIS of minimal cardinality in this special case.

Keywords: network flow problem, infeasibility, flow cut, IIS, Gale-Hoffman theorem, NP-hardness

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 03/17/2014
Entry Accepted: 03/17/2014
Entry Last Modified: 07/12/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society