Primal partitioning algorithms for structured linear and network programming problems

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.