Constrained network problems : theoretical and computational aspects

Abstract

Constrained network problems arise from the addition of general linear constraints to ordinary network problems. The resulting problem loses the special structure that has allowed the development of very efficient solution procedures for ordinary network problems. This dissertation analyzes the theoretical and computational aspects of constrained network problems so that efficient methods for solving very large-scale problems can be developed. The theoretical properties of the Lagrangian and surrogate dual programs of the constrained network problem are investigated. These properties are used to develop a surrogate and a Lagrangian constrained network optimization system which are implemented using state-of-the-art data structures. The resulting optimization systems are modified to exploit the capabilities of vector processing systems (supercomputers). Extensive computational testing is performed on very large-scale problems. This testing is performed on scalar and vector processers. The results indicate that the optimization systems developed by this study are the most efficient methods for solving constrained network problems.