Structural Redundancy in Large-Scale Optimization Models
Loading...
Authors
Bradley, Gordon H.
Brown, Gerald G.
Graves, Glenn W.
Subjects
Advisors
Date of Issue
1983
Date
1983
Publisher
Language
Abstract
This paper discusses automatic detection and exploitation of structural
redundancy in large-scale mathematical programming models. From our perspective,
such redundancy represents embedded special structure which can give significant
insight to the model proponent as well as greatly reduce solution effort. We report
experiments with real-life linear programming (LP) and mixed-integer (MIP) models in
which various methods are developed and tested as integral modules in an
optimization system of advanced design. We seek to understand the modeling
implications of these embedded redundancies as well as to exploit them during actual
optimization. The latter goal places heavy emphasis on efficient, as well as
effective, identification techniques for economic application to large models.
Several (polynomially bounded) heuristic detection algorithms are presented from our
work. In addition. bounds are reported for a maximum row dimension of the more
complex structures. These bounds are useful for objectively estimating the quality
of heuristically derived assessments of structural redundancy. Finally, some
additional suggestions are made for analyzing nonlinear programming (NLP) models.
Type
Book Chapter
Description
appears in Redundancy in Mathematical Programming, eds. Karwan, M., et al., Springer-Verlag.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Bradley, G., Brown, G.G., and Graves, G., 1980, “Structural Redundancy in Large-Scale Optimization Models,” appears in Redundancy in Mathematical Programming, eds. Karwan, M., et al., Springer-Verlag.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.