Nonconvex network optimisation : solution methods and applications. (1998)
Type of ContentTheses / Dissertations
Thesis DisciplineManagement Science
Degree NameDoctor of Philosophy
PublisherUniversity of Canterbury
AuthorsBell, Gavin J.show all
Nonconvex network flow models are used in a wide variety of problem domains involving discounting or economies of scale. Examples include network design, facility location, production planning, physical distribution, electricity transmission, and telecommunications problems. A variety of methods for solving nonconvex network flow problems have been developed in the literature; however, global optimisation of this class of problem is complex, and the convergence of the procedures slow. In this thesis we develop techniques that can be used to enhance standard solution procedures for nonconvex network flow problems. A general theory of concave underestimator analysis for such problems is presented. Based on this work, the theory of enhanced capacity improvement is developed and presented as part of a branch and bound solution algorithm for minimum cost mixed integer nonconvex network flow problems with side constraints. Computational analysis of this algorithm is described which shows the branch and bound algorithm incorporating enhanced capacity improvement provides a substantial performance increase over the same algorithm without capacity improvement. Finally we use and extend capacity improvement to develop an algorithm for the problem of short term electricity dispatch.