Extracting Embedded Generalized Networks from Linear Programming Problems

Loading...
Thumbnail Image
Authors
Brown, Gerald G.
McBride, Richard D.
Wood, R. Kevin
Subjects
Linear Programming
Generalized Networks
Basis Factorization
Computational Complexity
Heuristic Algorithms
Advisors
Date of Issue
1985
Date
1985
Publisher
Language
Abstract
If a linear program tLP) possesses a large generalized network (GN) submatrix, this structure can be exploited to decrease solution time. The problems of finding maximum sets of GN constraint s and finding maximum embedded GN sub matrices are shown to be NP-complete, indicating that reliable, efficient solution of these problems is difficult. Therefore, efficient heuristic algorithms are developed for identifying such structure and are tested on a selection of twenty-three real-world problems. The best of four algorithms for identifying GN constraint sets finds a set which is maximum in twelve cases and averages 99.1% of maximum. On average, the GN constraints identified comprise more than 62.3% of the total constraints in these problems. The algorithm for identifying embedded GN submatrices finds submatrices whose sizes, rows plus columns, average 96.8% of an LP upper bound. Over 91.3% of the total constraint matrix was identified as a GN submatrix in these problems, on average.
Type
Article
Description
Mathematical Programming, 32, pp. 11-31.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Brown, G.G., McBride, R., and Wood, R.K., 1985, “Extracting Embedded Generalized Networks from Linear Programming Problems,” Mathematical Programming, 32, pp. 11-31.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections