This dissertation deals with a primal-dual conjugate subgradient-based algorithm for solving large-scale and/or specially structured linear programming problems. The proposed algorithm coordinates a Lagrangian dual function and a primal penalty function which satisfies a flexible set of specified properties, in order to generate a sequence of primal and dual iterates which can be shown to converge to an optimal pair of primal and dual solutions. Besides producing both primal and dual solutions, this coordination of primal and dual functions serves to guide the crucial choice of step-sizes in the iterative algorithm, and also provides a natural stopping criterion based on the duality gap. The generic algorithm maintains a considerable degree of flexibility which permits one to exploit any special structures inherent in the problem. Moreover, the algorithm admits a rich variety of admissible penalty functions and dual formulations in designing a particular implementation scheme. Other algorithmic strategies that can be gainfully employed to improve the performance of the algorithm include space-dilation and box step techniques, pattern search strategies and suboptimization based on complementary slackness conditions. The algorithm is tested on three different transportation problems with additional constraints which are faced by the Freight Equipment Management Program of the Association of American Railroads. Problem 1 is a maximin problem in which ∫(x) = minimum {∫,(x), r=1, ... , R} is maximized subject to the transportation constraints and a total cost constraint, where ∫, (·) is a savings function for the r<sup>th</sup> railroad, for r=1, ... , R. Problem 2 minimizes weighted absolute deviations of ∫, (x); r=1, ... , R from its mean value subject to the Problem 1 constraint set. Problem 3, on the other hand, minimizes total cost subject to the transportation constraints and the constraint which requires each ∫, (x), r=1, ... , R to be at least at some desired level. Both theoretical issues concerning convergence properties and rates, as well as algorithmic design and computational performance issues are investigated. The results indicate that the algorithm is a viable strategy for these problems. In particular, a new conjugate gradient strategy emerges as a byproduct of this algorithm, which is shown to dominate other available strategies on standard test problems from the literature. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/77750 |
| Date | January 1988 |
| Creators | Ulular, Osman |
| Contributors | Industrial Engineering and Operations Research, Sherali, Hanif, Frendewey, James O., Koelling, C. Patrick, Sarin, Subhash C., Wang, C.C. |
| Publisher | Virginia Polytechnic Institute and State University |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation, Text |
| Format | x, 136 leaves, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | OCLC# 19763665 |
Page generated in 0.0025 seconds