AUTOMATIC IDENTIFICATION OF EMBEDDED STRUCTURE IN LARGE-SCALE OPTIMIZATION MODELS

This paper discusses automatic detection and expZoitution of embedded structure i n Large-Scale Linear Programming (LPI models. We report experiments with real-Zife LP and mixed-integer ( N I P) models i n which various methods are developed and tested as integraZ modules o f an optimization system o f advanced design [61. We seek t o understand the modeling implications of these embedded s t m t m e s as weZZ as to exploit them dming actual optimization. The l a t t e r goal pZaces heavy emphasis on e f f i-cient, as weZZ as e f fec t ive, identi f icat ion techniques for economic application t o large mode 2s. Several (po ZynomiaZZy compZex) heuristic aZgorCthms are presented from our work. In addition, bounds are developed for the maximum row dimension of the various factorizations. mese bounds are useful for objec-t ive Zy estimating the quality of heuxisticaZZy derived s true tures