We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
FINDING EMBEDDED NETWORK ROWS IN LINEAR PROGRAMS I. EXTRACTION HEURISTICS.
- Authors
Bixby, Robert E.; Fourer, Robert
- 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 ser aside certain rows and columns. Efficiency of the subsequent network extraction is dependent on the implementation, in predictable ways. Effectiveness is harder to exphin; 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.
- Subjects
HEURISTIC; OPERATIONS research; MANAGEMENT science; LINEAR programming; PROBLEM solving; MATRICES (Mathematics); NETWORK analysis (Planning); MATHEMATICAL programming; LINEAR substitutions
- Publication
Management Science, 1988, Vol 34, Issue 3, p342
- ISSN
0025-1909
- Publication type
Article
- DOI
10.1287/mnsc.34.3.342