DSpace Repository

Primal partitioning algorithms for structured linear and network programming problems

Show simple item record

dc.contributor.author Kearney, Trevor Daniel
dc.date.accessioned 2011-07-13T21:03:17Z
dc.date.accessioned 2022-10-27T00:29:45Z
dc.date.available 2011-07-13T21:03:17Z
dc.date.available 2022-10-27T00:29:45Z
dc.date.copyright 1984
dc.date.issued 1984
dc.identifier.uri https://ir.wgtn.ac.nz/handle/123456789/25311
dc.description.abstract This thesis presents the technical aspects of an algorithm that solves minimum cost network programming problems. Additionally, the optimal solution may be required to obey side constraints. These constraints may contain non-arc variables that have like arcs, their network counter-parts, upper and lower value bounds, and an objective function cost. This is a Linear Programming (LP) problem which has embedded in it large network structures. The emphasis of this thesis is on the theory and computer implementation of Primal Partitioning or Generalized Upper Bounding based algorithms. These algorithms specialize the revised simplex method to solve the above problem. Identifying that part of a problem is a network allows a large submatrix of the basis of the primal simplex algorithm to be stored by a spanning tree representation. This device enables the simplex operations to be performed much faster than if the network structure had not been exploited. Both storage requirements and numerical instability of primal partitioning codes is smaller than that exhibited by ordinary LP codes. Generalized Upper Bounding, Primal Simplex Network algorithms and Factorization is reviewed as this theory is used in, or is closely related to the primal partitioning algorithm. Multi-commodity Network problems and LP problems that have block angular coefficient matrices are discussed as the primal partitioning algorithm may be used to solve such problems efficiently. Study of these topics unify past research with current work and suggest ways how problem characteristics may be exploited in addition to network structures. Extensive reference is made to the SAS procedure PROC CNAPS, (Constrained Network Algorithm - Primal Simplex). This code enables a user to tune the algorithm for the particular network problem being studied, and change options and parameters to effect faster solution times. The facility for using the optimal solution of the unconstrained network as a warm start in later optimizations exists. So far, CNAPS has been used in large facility location distribution planning models of New Zealand's primary industries. en_NZ
dc.format pdf en_NZ
dc.language en_NZ
dc.language.iso en_NZ
dc.publisher Te Herenga Waka—Victoria University of Wellington en_NZ
dc.title Primal partitioning algorithms for structured linear and network programming problems en_NZ
dc.type Text en_NZ
vuwschema.type.vuw Awarded Research Masters Thesis en_NZ
thesis.degree.grantor Te Herenga Waka—Victoria University of Wellington en_NZ
thesis.degree.level Masters en_NZ
thesis.degree.name Master of Science en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account