Automatic Identification of Embedded Structure in Large-Scale Optimization Models
Abstract
This paper discusses automatic detection and exploitation of embedded structure in Large-Scale Linear Programming (LP) models. We report experiments with real-life LP and mixed-integer (MIP) models in which various methods are developed and tested as integral modules of an optimization system of advanced design. We seek to understand the modeling implications of these embedded structures 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 complex) heuristic algorithms are presented from our work. In addition, bounds are developed for the maximum row dimension of the various factorizations. These bounds are useful for objectively estimating the quality of heuristically derived structures.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1981
- Accession Number
- ADA598447
Entities
People
- Gerald G. Jerry Brown
- William G. Wright
Organizations
- Naval Postgraduate School