A characterization of irreducible infeasible subsystems in flow networks
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Wiley Blackwell
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111098 https://orcid.org/0000-0002-7488-094X |
| _version_ | 1811075430253330432 |
|---|---|
| author | Joormann, Imke Pfetsch, Marc E. Orlin, James B |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Joormann, Imke Pfetsch, Marc E. Orlin, James B |
| author_sort | Joormann, Imke |
| collection | MIT |
| description | 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 NP-hard. |
| first_indexed | 2024-09-23T10:05:45Z |
| format | Article |
| id | mit-1721.1/111098 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:05:45Z |
| publishDate | 2017 |
| publisher | Wiley Blackwell |
| record_format | dspace |
| spelling | mit-1721.1/1110982022-09-30T18:55:31Z A characterization of irreducible infeasible subsystems in flow networks Joormann, Imke Pfetsch, Marc E. Orlin, James B Sloan School of Management Orlin, James B 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 NP-hard. 2017-09-01T13:23:43Z 2017-09-01T13:23:43Z 2016-08 2014-03 Article http://purl.org/eprint/type/JournalArticle 0028-3045 1097-0037 http://hdl.handle.net/1721.1/111098 Joormann, Imke et al. “A Characterization of Irreducible Infeasible Subsystems in Flow Networks.” Networks 68, 2 (June 2016): 121–129 © 2016 Wiley Periodicals, Inc https://orcid.org/0000-0002-7488-094X en_US http://dx.doi.org/10.1002/net.21686 Networks Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley Blackwell Prof. Orlin via Shikha Sharma |
| spellingShingle | Joormann, Imke Pfetsch, Marc E. Orlin, James B A characterization of irreducible infeasible subsystems in flow networks |
| title | A characterization of irreducible infeasible subsystems in flow networks |
| title_full | A characterization of irreducible infeasible subsystems in flow networks |
| title_fullStr | A characterization of irreducible infeasible subsystems in flow networks |
| title_full_unstemmed | A characterization of irreducible infeasible subsystems in flow networks |
| title_short | A characterization of irreducible infeasible subsystems in flow networks |
| title_sort | characterization of irreducible infeasible subsystems in flow networks |
| url | http://hdl.handle.net/1721.1/111098 https://orcid.org/0000-0002-7488-094X |
| work_keys_str_mv | AT joormannimke acharacterizationofirreducibleinfeasiblesubsystemsinflownetworks AT pfetschmarce acharacterizationofirreducibleinfeasiblesubsystemsinflownetworks AT orlinjamesb acharacterizationofirreducibleinfeasiblesubsystemsinflownetworks AT joormannimke characterizationofirreducibleinfeasiblesubsystemsinflownetworks AT pfetschmarce characterizationofirreducibleinfeasiblesubsystemsinflownetworks AT orlinjamesb characterizationofirreducibleinfeasiblesubsystemsinflownetworks |