Extracting Embedded Generalized Networks from Linear Programming Problems
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.
Description
Mathematical Programming, 32, pp. 11-31.
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Extracting Embedded Generalized Networks from Linear Programming Problems
Brown, Gerald G.; McBride, Richard D.; Wood, R. Kevin (Monterey, California: Naval Postgraduate School, 1984-09); NPS55-84-020If 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 ... -
Automatic identification of embedded network rows in large-scale optimization models
Brown, Gerald G.; Wright, William G. (Springer, 1984);The solution of a large-scale linear, integer, or mixed integer programming problem is often facilitated by the exploitation of special structure in the model. This paper presents heuristic algorithms for identifying ... -
Automatic identification of embedded network rows in large-scale optimization models
Brown, Gerald G.; Wright, William G. (Monterey, California. Naval Postgraduate School, 1980-11); NPS55-80-030The solution of a contemporary large-scale linear, integer, or mixed-integer programming problem is often facilitated by the exploitation of intrinsic special structure in the model. This paper deals with the problem of ...