Data Structures for Generalized Network Algorithms

Abstract

Generalized network problems involve the optimization of a flow through a network. In contrast to normal networks, generalized networks include multipliers which alter the flow as it passes through the arcs. This enables the modelling of changes in flow caused by factors such as interest rates, as well as by processes such as energy conversion. Generalized network problems can be solved by using the simplex algorithm. However, if the simplex bases are represented as forests of quasi-trees, connected graphs with a single cycle, a far more efficient algorithm can be obtained. Matrix multiplications required by the simplex algorithm can be interpreted as traversals of the quasi-trees, and consequently many of the arithmetic operations can be replaced by logical operations. This increases the numerical stability of the algorithm. In this paper we outline this approach and discuss some of the data structures that can be used in its implementation. CR Categories and Subject Descriptors: G.1.6 Numerical Analysis: Optimization - Linear Programming; G.2.2 Discrete Mathematics : Graph Theory - Network Problems; E.1 Data Structures - Graphs and Trees General Terms: Algorithms Additional Key Words and Phrases: generalized networks, network optimization, quasi-trees 1. Introduction Generalized network models include the assignment, transportation and transshipment problems. The major advantage over these models is that the introduction of multipliers permits the modelling of problems where material appreciates, depreciates or changes from one form to another. The utility of generalized networks is 'illustrated by the many applications f 1,2,31. A generalized network model consists of a set of n nodes N and a set of arcs A. The problem is to find a flow xk (k E A) along each of the arcs such that: (a) it is of minimum cost (i.e. it minimizes I:ckxk); (1) (b) it satisfies the capacity constraints placed on the arcs (i.e. fk ~ck~ wk): and (2) (c) it is sufficient to meet certain demands d. (i E N) at each of the nodes. When di is negative, this is interpreted as a supply of (-d) units available at node i. For generalized networks this last requirement may be formulated as I: mkxk I: xk -- di (3) Arcs leading to Arcs leading from node i node i The coefficients mk are the multipliers, and they indicate by which factor the flow will increase ( or decrease) as it passes along the arc. The above equation states that the total flow into node i minus the total flow from the node should equal the demand, or the negative of the supply, at that node. The algorithm used to solve these models is derived from the simplex algorithm for linear programs, but, because of the special structure of generalized networks, the solution can be obtained thirty to fifty times faster than by means of a comparably sized linear program r 41. Past experience with this and a similar problem, namely the transshipment problem, has shown that the speed of the algorithm depends on the data structures used in its implementation. 2. Linear Programs and the Simplex Algorithm The generalized network problem, as formulated above, corresponds to the capacitated linear program Min c x subject to N X = d f ~ X ~ W (4) The coefficient matrix N has one column corresponding to 15