A primal-dual conjugate subgradient algorithm for large- scale/specially structured linear programming problems

Simple item page
dc.contributor.authorUlular, Osmanen
dc.contributor.committeechairSherali, Hanifen
dc.contributor.committeememberFrendewey, James O.en
dc.contributor.committeememberKoelling, C. Patricken
dc.contributor.committeememberSarin, Subhash C.en
dc.contributor.committeememberWang, C.C.en
dc.contributor.departmentIndustrial Engineering and Operations Researchen
dc.date.accessioned2017-05-24T18:18:54Zen
dc.date.available2017-05-24T18:18:54Zen
dc.date.issued1988en
dc.description.abstractThis 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.en
dc.description.degreePh. D.en
dc.format.extentx, 136 leavesen
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttp://hdl.handle.net/10919/77750en
dc.language.isoen_USen
dc.publisherVirginia Polytechnic Institute and State Universityen
dc.relation.isformatofOCLC# 19763665en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V856 1988.U574en
dc.subject.lcshLinear programmingen
dc.subject.lcshAlgorithmsen
dc.titleA primal-dual conjugate subgradient algorithm for large- scale/specially structured linear programming problemsen
dc.typeDissertationen
dc.type.dcmitypeTexten
thesis.degree.disciplineIndustrial Engineering and Operations Researchen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V856_1988.U574.pdf
Size:
6.27 MB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations