Extracting Embedded Generalized Networks from Linear Programming Problems
Brown, Gerald G.
McBride, Richard D.
Wood, R. Kevin
MetadataShow full item record
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.
Mathematical Programming, 32, pp. 11-31.
Showing items related by title, author, creator and subject.
Thomen, David S.; Brown, Gerald Gerard (Monterey, California. Naval Postgraduate School, 1980-01); NPS-55-80-003To solve contemporary large scale linear, integer and mixed integer programming problems, it is often necessary to exploit intrinsic special structure in the model at hand. One commonly used technique is to identify and ...
Dewald, Lee Samuel (1985);Time series models with autoregressive , moving average and mixed autoregressive-moving average correlation structure and with symmetric, heavy-tailed, non-normal marginal distributions, called Jl -Laplace, are consid ...
Schneidewind, Norman F. (IEEE, 1993-11);In the use of software reliability models it is not necessarily the case that all the failure data should be used to estimate model parameters and to predict failures. The reason for this is that old data may not be as ...