Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics

Robert E. Bixby and Robert Fourer
Additional contact information
Robert E. Bixby: Department of Mathematical Sciences, Rice University, Houston, Texas 77251
Robert Fourer: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60201

Management Science, 1988, vol. 34, issue 3, 342-376

Abstract: An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. We examine three broad classes of heuristic techniques---row-scanning deletion, column-scanning deletion, and row-scanning addition---for the extraction of large embedded networks. We present a variety of implementations, and compare their performance on realistic test problems. The success of our tests depends, in part, on several preprocessing steps that scale the constraint matrix and that set aside certain rows and columns. Efficiency of the subsequent network extraction is dependent on the implementation, in predictable ways. Effectiveness is harder to explain; the more sophisticated and expensive implementations seem to be most reliable, but much simpler implementations sometimes find larger networks. The largest networks are obtained by applying a final augmentation phase, which is studied in the second part of this paper.

Keywords: programming: linear; algorithms (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.342 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:342-376

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().