Nonlinear optimisation on multicommodity networks

Backhouse, Allan R. (1996) Nonlinear optimisation on multicommodity networks. PhD thesis, Murdoch University.

Abstract

The purpose of the work described by this thesis is the exploration and comparison of a selection of methods for the solution of multicommodity network optimisation problems that have a nonlinear objective function, bound constraints, and both linear and nonlinear side constraints (these problems are denoted by MSC-NL).

The motivation for this work was an important class of problems that arise in the petroleum industry. These problems typically have a relatively small number of nonlinear constraints which are, unfortunately, not convex. In many cases, a realistic model of a "real world" problem leads to optimisation problems which, for nonlinear programming problems, are medium to large in size and yet it is desirable for local optima to be able to be determined using easily accessible computing environments. Hence, it is important for methods to be available that are able to exploit the sparsity and structure inherent in the problem, are efficient in computer processing time and memory use, and are reliable and numerically stable. A variety of methods that potentially meet these requirements have been implemented in an experimental computer code called NLNET.

Three different general nonlinear programming methods are considered: projected Lagrangian, penalty multiplier, and generalised reduced gradient. For each of these methods, the implementation in NLNET uses the same multicommodity network solver. This solver is an implementation of the active set feasible direction method that is specialised for multicommodity network optimisation problems with a nonlinear objective function and linear side constraints. Within this solver a number of different approaches, for details such as partitioning of the constraint matrix and determining a search direction, have been implemented. It is very common to encounter degenerate bases when using NLNET to solve problems of type MSC-NL and hence cycling is of concern. Consequently, methods are considered that either avoid generating an infeasible search direction or determine a feasible direction if an infeasible direction has been obtained. The multicommodity network solver is, in turn, based on a well known specialisation of the revised simplex algorithm to linear multicommodity network problems that has been extended to be able to handle side constraints.

A major thrust of this work is the comparison of different combinations of a number of selected methods and approaches, some of which have been mentioned above, that can be used to solve MSC-NL. This comparison is made by presenting and analysing the results obtained by using NLNET on a test problem set consisting of thirteen "real world" petroleum industry problems.

Item Type:	Thesis (PhD)
Murdoch Affiliation(s):	School of Physical Sciences, Engineering and Technology
Notes:	Note to the author: If you would like to make your thesis openly available on Murdoch University Library's Research Repository, please contact: repository@murdoch.edu.au. Thank you.
Supervisor(s):	Kloeden, Peter
URI:	http://researchrepository.murdoch.edu.au/id/eprint/51547

Item Control Page