Extracting Embedded Generalized Networks from Linear Programming Problems

Simple item page
dc.contributor.authorBrown, Gerald G.
dc.contributor.authorMcBride, Richard D.
dc.contributor.authorWood, R. Kevin
dc.contributor.departmentOperations Research (OR)
dc.date1985
dc.date.accessioned2014-01-09T22:21:13Z
dc.date.available2014-01-09T22:21:13Z
dc.date.issued1985
dc.descriptionMathematical Programming, 32, pp. 11-31.en_US
dc.description.abstractIf 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.en_US
dc.identifier.citationBrown, G.G., McBride, R., and Wood, R.K., 1985, “Extracting Embedded Generalized Networks from Linear Programming Problems,” Mathematical Programming, 32, pp. 11-31.
dc.identifier.urihttps://hdl.handle.net/10945/38134
dc.rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.en_US
dc.subject.authorLinear Programmingen_US
dc.subject.authorGeneralized Networksen_US
dc.subject.authorBasis Factorizationen_US
dc.subject.authorComputational Complexityen_US
dc.subject.authorHeuristic Algorithmsen_US
dc.titleExtracting Embedded Generalized Networks from Linear Programming Problemsen_US
dc.typeArticleen_US
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
extractingembeddedgeneralizednetworks.pdf
Size:
9.83 MB
Format:
Adobe Portable Document Format
Download
Collections
Publications