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
