Finding Embedded Network Rows in Linear Programs I: Extraction Heuristics
Abstract
An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. In this paper, 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 describe a variety of implementations, and compare their performance on varied 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 more reliable, but much simpler implementations sometimes find equally large networks. The largest networks are obtained by applying a final augmentation phase, which is studied in the second part of this paper.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1986
- Accession Number
- ADA455195
Entities
People
- Robert E. Bixby
- Robert Fourer
Organizations
- Rice University