NPS5582012
NAVAL POSTGRADUATE SCHOOL
Monterey, California
SOLVING GENERALIZED NETWORKS
by
Gerald G. Brown
and
Richard D. McBride
March 1982
Approved for public release; distribution unlimited
Prepared for:
M — 1 Postgraduate School
FEDDOCS )re *> California 93943
D 208.14/2
NPS5582012
P< ZZOIZ
NAVAL POSTGRADUATE SCHUUL
MONTEREY, CALIFORNIA
Commodore K. H. Shumaker uavid A  ^chrady
Superintendent Provost
Reproduction of all or part of this report is authorized.
UNCLASSIFIED
SECURITY CLASSIFICATION OF THIS PAGE (Whtn Data Entered)
SkR£V CA 939435101
REPORT DOCUMENTATION PAGE
READ INSTRUCTIONS
BEFORE COMPLETING FORM
1. REPORT NUMBER
NPS5582012
2. GOVT ACCESSION NO
3. RECIPIENT'S CATALOG NUMBER
4. TITLE (and Subtitle)
SOLVING GENERALIZED NETWORKS
5. TYPE OF REPORT & PERIOD COVERED
Technical Report
March 19 3 2
6. PERFORMING ORG. REPORT NUMBER
7. AUTHORS
Gerald G. Brown
Richard D. McBride
8. CONTRACT OR GRANT NUMBERS
9. PERFORMING ORGANIZATION NAME AND ADDRESS
Naval Postgraduate School
Monterey, CA 93943
10. PROGRAM ELEMENT, PROJECT, TASK
AREA & WORK UNIT NUMBERS
II. CONTROLLING OFFICE NAME AND ADDRESS
Naval Postgraduate School
Monterey, CA 93943
12. REPORT DATE
March 1982
13. NUMBER OF PAGES
60
14. MONITORING AGENCY NAME & ADDRESS^' different from Controlling Office)
15. SECURITY CLASS, (of thlt report)
Unclassified
15«. DECLASSIFI CATION/ DOWN GRADING
SCHEDULE
16. DISTRIBUTION STATEMENT (ol this Report)
Approved for public release; distribution unlimited.
17. DISTRIBUTION STATEMENT (of the mbatract entered In Block 20, II different from Report)
18. SUPPLEMENTARY NOTES
19. KEY WORDS (Continue on reverse elde if neceeamry and Identity by block number)
Generalized Networks, Flow Networks, Minimum Cost Flow Networks,
Generalized Transshipment Problem, Primal Simplex Network
Optimization
20. ABSTRACT (Continue on reverae aide It neceeamry and Identity by block number)
A complete, unified description is given of the design, implemen
tation and use of a family of very fast and efficient large scale
minimumcost (primal simplex) network programs. The class of
capacitated generalized transshipment problems solved includes the
capacitated and uncapacitated generalized transportation problems
and the continuous generalized assignment problem, as well as the
pure network flow models which are specializations of these
DD , ^ N RM 73 1473
EDITION OF 1 NOV 65 IS OBSOLETE
S/N 0102 LF0146601
UNCLASSIFIED
SECURITY CLASSIFICATION OF THIS PAGE (Whan Data Bnfred)
UNCLASSIFIED
SECURITY CLASSIFICATION OF THIS PAGE (Whan Dmtm Bnftud)
problems. These formulations are used for a large number of
diverse applications to determine how (or at what rate) flows
through the arcs of a network can minimize total shipment costs,
A generalized network problem can also be viewed as a linear
program with at most two nonzero entries in each column of the
constraint matrix; this property is exploited in the mathematical
presentation with special emphasis on data structures for basis
representation, basis manipulation, and pricing mechanisms. A
literature review accompanies computational testing of promising
ideas, and extensive experimentation is reported which has pro
duced GENNET, an extremely efficient family of generalized
network systems.
S'N 0102 LF 0146601
UNCLASSIFIED
SECURITY CLASSIFICATION OF THIS PAGEfWhen Datm Entafd)
SOLVING GENERALIZED NETWORKS
by
Gerald G. brown
Naval Postgraduate School
Monterey, CA 93943 USA
and
Richard D. McBride
University of Southern California
Los Angeles, CA 9UUU" 7 USA
August 1981
(Rev 84.U2.U1)
(Copyright ly84)
DUDLEY KM
■
ABSTRACT
A complete, unified description is given ot the design,
implementation and use of a family ot very fast and etticient
larye scale minimumcost (primal simplex) network proyrams.
The class ot capacitated generalized transshipment problems
solved includes the capacitated and uncapaci tated generalized
transportation problems and the continuous generalized assign
ment problem, as well as the pure network flow models which are
specializations ot these problems. These formulations are used
for a large number of diverse applications to determine how (or
at what rate) flows through the arcs of a network can minimize
total shipment costs. A generalized network problem can also
be viewed as a linear program with at most two nonzero entries
in each column ot the constraint matrix; this property is ex
ploited in the mathematical presentation with special emphasis
on data structures for basis representation, basis manipulation,
and pricing mechanisms. a literature review accompanies compu
tational testing ot promising ideas, and extensive experimenta
tion is reported which has produced GfciMNhiT, an extremely effi
cient family of generalized network systems.
1 . INTRODUCTION
This paper reports the development ot a laryescaie primal
network code tor solving capacitated generalized transshipment
problems. The capacitated generalized transshipment problem is
the most general of the minimum cost tlow models in continuous
variables, whicn include the capacitated and uncapaci tated trans
portation problems and the continuous generalized assignment problem
as well as the pure network specializations ot these problems.
These models are used tor a large number ot diverse applications
that include transportation ot goods, desiyn ot reservoir, com
munications, and pipeline systems, assignment ot personnel ana
machinery to jobs, bid evaluation; currency exchange and cash
management; production, sales and inventory planning; and many
others. For further discussion of these applications see survey
articles such as Bradley [bj, or Glover et al., [17, 18], and
textbooks (as well as their cited references) such as Dantzig
[13], Jensen and Barnes [23], and Kennington and Helgason [27],
The capacitated generalized transshipment model and its
specializations are minimumcost network flow problems. The
goal is to determine how (or at what rate) flows through the
arcs ot a network can minimize shipment costs. The network is a
directed graph, G , defined by a set ot nodes, N , and a set ot
arcs, A , with ordered pairs ot nodes (tail, head) as elements
indexed by k: ( t , t, ) . for each arc there is a shipping cost
per unit tlow, c , a minimum allowable tlow (or lower bound),
I, , and a maximum allowable tlow (or upper bound, or capacity),
u
k
In addition, there are coefficients (or multipliers, or gains,
or losses), a and b, which can change the magnitude of (or
— K K
amplify, or attenuate) each unit of flow respectively entering
and leaving arc k . Each node is either a supply node where
units of the good enter the network, a demand node where units
leave, or a transshipment node. The problem is to minimize
total costs with flows, x, , that satisfy the associated lower
and upper bounds and preserve the conservation of flow at each
node :
(GN)
MIN I c, x
keA
k k
s . t .
i
keA
with f, =i
k
a. x.
— k k
keA
with t. =i
x, = b
i e N
\ < x R < u R ,
keA,
where :
b i ■
supply if i is a supply node;
 demand it i is a demand node;
U otherwise.
Note that any linear program with at most two nonzero coefficients
associated with each variable is a generalized network (GN). for
mulation (Gin) is a generalized transshipment model (GT) if all a.
are +1, in which case the corresponding coefficient is called the
multiplier m, = b. . For purposes of exposition, we will address
(GT) since assuming the existence of a finite upper bound on each
variable it is possible to transform the (GN) coet t icientsby
scaling or by reflecting variables with respect to their upper
boundsso that one coefficient is +1 tor each variable. The other
coefficient for each variable then becomes the multiplier value,
m. , and the generalized transshipment (GT) network flow interpre
tation results with a node tor each constraint and a directed arc
tor each variable. If a variable has two nonzero coet t icients , its
arc is directed away from the node corresponding to the constraint
with the +1 coefficient; a variable with just one nonzero coefficient
(±1) corresponds to an arc forming a selfcycle, leaving and
returning to the same node.
Some generalized networks (GN), such as those obtained by
relaxing integer restrictions on flow variables, cannot be scaled
conveniently to (GT). These (GN) are accommodated by obvious minor
modifications in the following (GT) presentation. We have developed
codes tor solving (GN) and specialized them tor ( GT ) problems.
Generalized networks can be solved as linear programming
problems, but contemporary commercial linear programming sys
tems consume much more computer time and data storage region
than special purpose network codes. Indeed, the advantage of
network codes is so pronounced that it is even worthwhile to
develop special linear programming procedures to exploit intrin
sic network structure found embedded within more general models
(e.g., Kennington and Helgason [27J, McBride [3U], Brown and Graves
[8], and Brown and McBride [9]). Brown and Wright [11] and Brown,
McBride and Wood [10] show that many reallife linear programs
contain a large embedded generalized network structure.
3
These models are widely used because they accurately de
scribe a large variety of important applications. Generalized
networks not only directly represent gains with m, > 1 (e.g.
interest return on investment, heat gain, etc.) and losses with
< m, < 1 (e.g., evaporation, voltage drop, attrition, etc.)
rK
in the flows, but also admit conversions of units for these flows
(e.g., machine time to output pieces, lira to yen, etc.). In
addition, m, < represents situations without obvious physical
K
flow interpretation (e.g., flows which "enter the head" of arc k
in proportion m. of those entering the tail), but which nonethe
less provide valuable modelling tools. There has been continuing
growth of interest in network models because efficient computer
programs have made possible the reliable, economic solution of
problems with more variables than virtually any other optimiza
tion technique (e.g., the pure network system, GNET [6], has been
installed at hundreds of sites worldwide and is now cited as a
routine research tool). Perhaps most important, networks are
readily accepted by nonanalysts and are consequently extremely
popular operations research models.
Although several papers have been written in this general
area, and significant computational breakthroughs have been
reported, there has not previously been a single, unified de
scription of a complete implementation, nor have "new generation"
computer programs been made generally available to the academic
community. Here we report the research and computational experi
ments which have produced GfcJNNET, an extremely efficient family
of network optimization systems. GENNET exploits pure network
structure embedded in generalized networks, and specializes in
trinsically to GNET lb], when both systems are applied to pure
networks, (the floating point arithmetic in) GENNET requires
about lb percent more time than GNET. An important objective ot
this paper is to make these new approaches easily accessible to
a wide audience via a clear exposition and concrete examples of
efficient FORTRAN programs. Further, the availability ot the
( GT ) and (GN) computer programs will now make it possible tor
other investigators to reproduce and extend our experimental
results .
Bradley, Brown and Graves lb] trace the historical develop
ments leading to contemporary primal simplex pure network algo
rithms, their supporting data structures, and etticient imple
mentations such as GNET. For other subclasses ot generalized
networks, algorithms have been reported by Jewell [2b], Eisemann
[14], Maurras [2y], Glover, Hultz, Klingman and Stutz [17,la,ly],
Balachandran [2], and Jensen and Bhaumik 124]. An efficient
algorithm for large generalized network problems has been de
veloped by Glover, Klingman, Hultz, Stutz, Karney and Elam
[15,17,18,21,22]. However, their contributions are scattered
among the papers referenced; Kennington and Helgason [27] and
Jensen and Barnes [23] provide textbook descriptions of compu
tations apparently gleaned from these papers, providing an ade
quate treatment of the graphical algorithm with more computational
advice than the seminal presentation by Dantzig [13] but tew
details ot etticient basis updating.
2. THE APPROACH
Our approach continues with generalized networks in pre
cisely the philosophical vein of the pure network exposition
of Bradley, Brown and Graves: we seek data structures and algo
rithms that yield efficient implementations without abandoning
the flexibility of a general largescale mathematical program
ming perspective [6, p. 3 ff]. We introduce few of the details of
the general boundedvariable simplex algorithm, and we repeat
little of the underlying pure network material; the assiduous
reader might well review the prior paper for which this is an
intimate companion.
We continue with a brief description of the algebraic
specialization of the simplex method for generalized networks.
Specific design decisions and experiments carried out with GENNET
are described, including computational tests of alternate ap
proaches. Some extensions of GENNET are presented to further
exploit special problem structure.
J. GENERALIZED NETWORK SPECIALIZATION
Efficient primal simplex specialization to the generalized
network case depends upon the wellknown result that any
generalized network basis can be put in neirly (upper) tri
angular form by simple permutation of rows and columns. This
inherent near triangularity can be exploited by direct solution
of the simplex equations with modif ied forward, or back substi
tution. Fortuitously, this basis structure also leads to ex
tremely fast solution updates orchestrated in concert with
efficient dynamic reorganization of each new basis.
Theorem (e.g., Uantzig [13]) Any basis B extracted from a
generalized network problem can be put in the form (1) by
rearranging rows and columns .
,P
(1)
where each square submatrix component B is either upper
triangular or nearly upper triangular with only one element
below the diagonal .
Proof. Our proof is constructive. We know that the basis has at
least one nonzero entry in each row, and one, or two,
entries in each column. Define a pairing as the associ
ation of a row with a column sharing an entry in b , a
deferral as a temporary deletion of a pair from consider
ation, and an ass ignment as the fixing of a pair on the
diagonal in the ordering of the rearranged sequence,
followed by the assignment of all deterred pairs which
have a column with an entry in an assigned row.
Step 1) Defer singleton rows . Locate a row with one entry, pair
the row with the column of the entry and defer the pair.
Repeat Step 1 until no row remains with one entry.
Comment: Step 1 reduces B to a submatrix with exactly two
entries in each row and in each column . To see this,
note that each column can have at most two entries, or
2m entries for m columns. Each row has at least two
entries. Suppose that some row has more than two
entries; then at least 2m + 1 entries exist, leading to
a contradiction. Thus, exactly 2m entries remain;
consequently, each column has exactly two entries, as
does each row.
Comment: Step 1 deters an upper triangular set of pairs. To
see this, diagonalize the pairs in reverse of the order
of their deferral, and place this sequence at the end
of the rearrangement of B .
Comment: A sequence of assignments in the rearrangement begins.
step 2) Assign a Component .
2.1) If a row remains which is neither assigned nor deterred,
begin a near triangular component: pair the row and a
column and ass ign this pair next in the rearranged
sequence. utherwise, go to Step 2.3.
2.2) Apply Step 1 and ass ign each newly deterred pair next in
the sequence. Go to Step 2.4.
2.3) begin a triangular component: assign the most recently
deferred pair next in the sequence.
2.4) Repeat Step 2 until all rows and columns are assigned.
Comment: It Step 2.1 assigns a pair to a component, then the
component is nearly triangular with one element below
the diagonal in the first column. utherwise, the
component is triangular.
Consider the generalized network problem given in Figure 1,
a generalized transshipment problem with 2 sources, 1U sinks,
15 nodes, and 3U arcs. toe will use this problem to illustrate
concepts and etticient solution methods. In this problem the
multipliers are all positive. tor arc k directed trom node
i to node j , if tlow x, leaves node i , then ^i^k
arrives at node j . When m > 1 the amount arriving at node
j is greater than the amount leaving node i . This would be
the case in cash flow problems when the arc corresponds to an
investment ana m, = (1 + r. ) with r_, the rate of return.
When m, < 1 then the amount arriving at node ] is less than
— k
the amount leaving node i . here the loss could correspond to
evaporation, taxation, transmission loss, brokerage fees, seepage
or deterioration. Pure network arcs are indicated by m. = 1
— k
(and may be even more abundant in real problems than in our
example,). for clarity, minimum allowable flows are zero, and
maximum allowable flows are not specified.
Arc
from
To
Cost
Multiplier
k
f k
fc k
C k
^k
1
4
3
33.84
.99
Node
Supply
2
3
2
1
3
5
15.47
53.54
1.00
.74
1
22.86
4
2
5
26.76
.74
2
177.14
5
3
5
73.49
1.00
6
5
5
52.52
1.00
Node
Demand
7
3
6
35.12
.91
8
5
6
11 .12
1 .00
6
19.39
9
4
7
59.56
1.17
7
3.64
10
2
7
88.38
1.06
8
24.92
11
4
8
84.12
1.00
9
9.38
12
2
8
21 .86
.92
10
14.07
13
4
9
3.46
1.00
11
56.91
14
3
9
29.72
1 .00
12
2.45
15
4
10
6.12
1.00
13
30.93
16
2
10
31.08
.96
14
21.76
17
3
10
1.07
1.07
15
16.55
18
5
10
44 .44
1 .00
19
1
11
67.15
.91
20
2
11
59.83
.79
21
3
11
50.46
1.17
22
5
11
71.42
1 .00
23
2
12
8.88
1 . 18
24
1
13
28. 22
.83
25
4
13
77.34
1.00
26
3
13
45.60
1 .00
27
5
13
20.67
. 88
28
4
14
37.76
1.13
29
2
14
18. 16
.98
3U
3
15
67.62
1 .00
Figure 1. A Single Commodity Generalized Transshipment
Problem ( GT )
10
figure 2 shows a basis for the problem introduced in
Figure 1. (In this simple case, there is only one component:
p = 1.)
A unique subgraph partition ot G denoted G corre
sponds to b . Let A = {a^la 1 is an arc associated with b J
a column ot b} , then G^ = [N,A. J denotes the directed graph
£
associated with the basis B . To each submatrix b ot b
£ £ £
there corresponds a component ot G denoted by G = [w ,A ] .
£ £ £
N is the set ot nodes corresponding to the rows ot b and A
£
is the set ot arcs corresponding to the columns ot B . It is
£
known (e.g., [13]) that G is either a rooted tree or a one
l
tree (a tree with an additional arc forming one cycle). If G
£ £
is a rooted tree, then B is upper triangular. If G is a
£
is a onetree, then B is upper triangular except tor one
element below the diagonal. Each component can be viewed as
having one cycle if we assert that each rooted tree has a self
cycle corresponding to its root node.
In our example basis, the subgraph G has only one com 
pone nt , (onetree) shown in Figure 2: G is a onetree, with
nodes 2, 3 and 11 composing its cycle.
As in the pure network case, this near tr iangulat ion and
associated subgraph are naturally represented by a pre decessor
t_uncticm p( ), and a predecessor graph (which does not preserve
the orientation of arcs in the original network). The predeces
sor function can be used iteratively to construct the unique
backpath from any node to the root (or cycle); the backpath
includes all nodes on the cycle. The immedia te successors ot a
11
Column
2 4 12 29 23 10 20 21 17 26 24 7 30 14 13
Row
2
5
14
12
7
11
3
10
13
1
6
15
9
4
11111
.74
.92
.98
1.18
! 1 1

1
11.06
.79 1.17
111 111
1.07
1.0 j .83
i
1
.91
1.0
1.0 1.0
A Preorder NearTriangulation
(The underlined coefficient is below the diagonal.)
Join
00000 0©0©0
t t
OneTree
Figure 2. A Generalized Transshipment Basis
(For the problem in Figure 1.)
12
node, if any, are the first nodes encountered on all paths ex
cept the backpath to the root, and all the nodes on these paths
are called successors .
Note that each basis may have many near tr ianyulat ions .
However, all such near trianyulat ions yield the same predecessor
function and graph (where the right to left ordering of succes
sors of any node is immaterial). Thus, the predecessor graph
does not completely represent a near tr iangulat ion without
additional information: an ordering of the rows (nodes). For
algebraic reasons, we restrict such partial ordering to preorder
[6], in which a node i always precedes its successors, if any
and in which all its successors, if any, precede any node which
does not precede node i .
13
4. IMPLEMENTATION
For didactic reasons, we bey in by introducing a complete
primal generalized network algorithm using a preorder traversal
method. Controversial alternatives are deferred until this
paradigm is presented. Hereafter, notation with upper case
roman letters followed by parentheses indicates a program data
array. For instance, the predecessor array is referred to as
P( ).
Static arc storage is used for tails T( ), heads H( ),
costs C( ), multipliers MUL( ), and capacities CP( ). Contigu
ous storage by tail, or by head node reduces T( ) , or H ( ) to
an hierarchical nodelength entry point array. (GENNET uses
contiguous storage by head node, as does GNET.) Lower bounds
on arc flow are translated out prior to solution, with appropri
ate adjustment of the initial righthand side of (GT), and of
CP( ). The sign bit of CP( ) is available to indicate arcs
nonbas ic at their upper bounds ( ref lected with flow CP( ) ).
The predecessor function and its array P( ) are defined
so that the basic arcs in a cycle are oriented uniformly in a
directed cycle. All basic arcs not on a cycle are oriented so
that a backpath is created to a cycle. To obtain this orienta
tion the direction of some arcs must be reversed, and the sign
bit of the predecessor array is used to indicate: if P(I) < 0,
then the orientation of arc (I, P(I)) is reversea from its
original orientation.
This is the complement of the discipline used in GNET [6]
14
A depth array D( ) reveals for each node the number of
nodes on the backpath before encountering a cycle. Nodes on a
cycle have depth zero. Number of successors , or preorder
distance are acceptable substitutes tor depth [6], but are not
discussed here.
A preorder traversal array IT( ) is maintained so that all
preorder successors of a cycle node are encountered before
another cycle node. It is convenient to make this a circular
list for each near triangular basis component by setting IT( )
of the last preorder node in the component equal to the first
preorder node in the component.
The components of G are not interconnected, or equiva
i
lently, the submatrices B in (1) do not have common rows or
columns. Consequently, the p components of a basis may be
represented in a single set of nodelength arrays.
The array X( ) contains the values of basic variables,
values of dual variables (or simplex multipliers, or node poten
tials) are stored in U( ), and IVAR( ) gives the location of
basic variables in the arc arrays. The array FAC ( ) contains
the cycle factors , defined later. figure 3 shows these arrays
for the basis given in figure 2.
Generalized networks do not exhibit totally unimodular
bases. Consequently, floating point representation is required
for x( ), u( ) and FAC ( ), and is desirable for arclength arrays
C( ) , MUL( ) , and CP( ) .
15
Node Predecessor Depth Traversal basic Variable Dual Cycle Factor
P( )
D( )
IT( )
IVAR( )
X( )
U( )
FAC ( )
1
13
2
6
24
22.860
16.665
*
2
3
5
2
118.169
47.148
.48101
3
11
1U
21
45.826
31.678
.48101
4
9
2
2
13
0.0
5.418
*
5
2
1
8
4
0.0
27.552
*
6
3
1
15
7
21.308
3.782
*
7
2
1
11
10
3.434
38.898
*
8
2
1
14
12
27.U87
27.487
*
y
^3
1
4
14
9.380
1.958
*
10
3
1
13
17
13.150
28.606
*
n
2
3
20
4.170
16.053
.48101
12
2
1
7
23
2.076
32.431
*
13
3
1
1
26
11.956
13.922
*
14
2
1
12
29
22.204
29.580
*
15
3
1
y
30
16.550
35.942
*
Figure 3. GENNtT Basis Representation Arrays
(for Basis in Figure 2)
16
Step Si, Priceout
The reduced cost for nonbasic arc k , oriented from f.
k
to t, is (given the current dual solution u and column N ):
r. = c,  uN
k k
= c k " u f + ^kV
k k
= C(k)  U(f ) + MUL(k)*U(t, ) .
K K.
(If CP(k) < 0, arc k is reflected and the siyn of r, is
reversed.) At most, one multiplication, addition and subtrac
tion are required. Note that the multiplication is unneccessary
if  m,  = 1; further specialization is possible for sets of
priced arcs with common attributes. If arc k is a logical arc
(slack, artificial, or surplus variable) then C(k) can be
logically generated, rather than explicitly stored, and
r k = C(k) ± U(f R
depending upon the sign of P(f ) .
K
i
From the example,
r 2l =? C(Z1)  U(b) + MUL( zl )*U( li)
= 2U.57  (27.552) + ,8b(13.922)
= 19.133 .
17
This variable will be used as the entering nonbasic variable
for further illustration.
Step S2, Ratio Test
For the determination of the arc to leave the basis the
system of equations
BZ k = w k ,
k k
must be solved for the transformed column Z . ( N is
used if arc k is reflected.) Due to the near triangularity
of B , this incoming column transformation can be combined
with the ratio test in a single integrated process.
Suppose that N has two nonzero coefficients representing
an arc oriented from f, to t, , and that the arc is not
reflected. An apparent complication arises if f and t, are
s t
in separate components of B in (1), say B and B , respec
tively. In this case two disjoint subsystems must be solved and
the results added to determine the nonzero elements in Z
The subsystems are:
B (J = e f , and
k
B fc g k = m R e ,
k
18
f k t k
(e is the t, th unit vector; (J and Q are disjoint
k
k
components of Z . )
This complication is inconsequential. In order to see
this/ consider solving one of the systems:
ut„ fc k
b g = m.e
k
The only nonzero elements of Q will be those that correspond
to the nodes in the backpath from node t . As we shall see,
this follows from the manner in which the coefficient m, in
— k
row t propagates during substitution solution.
K.
Suppose that G is a rooted tree. The backpath from node
t, can be denoted by iteration of the predecessor function: t ,
K. K
p(t, ), p(p(t )),..., root; this sequence is shown below as a,
K K
dl,...,0, analogous to the backpath length remaining to the root
Root
P(p(t k ))
l d2
d1
P(t k )
l dl
19
The values of a and b for each basic arc depend upon the
original orientation of the arc, given by the sign of P( ).
For original orientation, P( ) > implies that a = +1 and b
is the multiplier value, P( ) < U reverses these definitions.
The triangular system corresponding to this backpath is:
a Q b x
a d2 b dl
a dl b d
Q
U
•
u
m,
By back substitution, its solution is:
m,
— k
— d
g 6 = " b 6+l q 6+l =
3 6
Now suppose that G is a onetree. Let node t, be on the
cycle. The backpath is t , p(t. ) , p(p(t, )), ..., c, with
p(c)
t and length p ; this sequence is shown below as
1 ,2 , . . . , p , analogous to the backpath length beyond the cycle
start .
20
The corresponding near triangular system is
a b ,,
p p+1
'P + 1
a 3 b 2
~P
a 2 b l
l l
m,
By modified back substitution, its solution is
_m k 1
" b 6+l q 6+l
for 6 = 2, . . . ,p ,
where
p b.
f = l  n
6=l a 6
21
The cycle factor (or loop factor [13]), f , is common to all
nodes in the cycle and can be computed when the cycle is
created and stored in FAC ( ) for all nodes on the cycle so
that it is immediately available at this step.
Suppose that the entering arc is ( f , t. ) with coefficient
entries (a,,b ) and that the f, and t backpaths converye.
Using nomenclature for the backpath sequences introduced above,
the corresponding system is:
join
a u b i
3 £l b £
w
w
d1 d
a dX b d
22
by back substitution, its solution is:
b k
q, = — , ( d begins t. backpath sequence),
Q a . k
— d
" b 6+l q
6+1^6+1
for 6 = d, d1 , . . . , r ,
l d a
, (d bey ins f, backpath sequence) ,
" b 6+l q 6+
tor 6 = d, d1 , . . . ,w ,
<±o
ii
 (b w^w + b rV
a £l
b 6+l q 6+i
q x = tor 6 = 12 , 1 i , . . . , U .
Suppose that entering arc (f, , t, ) with coetticients
(a, ,b. ) enters and that the backpaths converge on a cycle. The
corresponding system is:
23
a p b p + l
a p+l
a *l h l
w
■*
a b
s1 s
s
a 2 b l
~P
1
a b ^i
w w+1
a w+l
a dl b d
a r b r+l
a r+l
\
a dl b d
24
By modified back substitution, its soiution is:
q. = — — , (d bey ins t, backpath sequence) ,
l d a
" b 6+i q 6+
for 6 = d, di , . . . , r,
"b q
381
r^r
X
a , t
s1
" b 6 + i y 6 + l
for 6 = s2 ,...,£, £1 ,... ,s ,
q, = — , (d begins t, backpath sequence) ,
q a , k
d
b 6+i q 6+l
for 6 = d , . . . ,w ,
<J»i *
b q
* a *i t
D 6+l q &+l .
q,. = for 6 =
X £ f % • • f P ( ~Ir*«*fO/«*«/ JC /
q. = q„ + q, tor 6 = l,...,p .
25
For the cycle in Figure 2,
i (1) (1) (1.17)
f = X J  x ^779 x 1
= .481U1 .
By now it should be apparent that one composite back sub
stitution scheme will suffice for all cases. The cycle factor
is applied once when, and if, a cycle is encountered on a
backpath .
If the backpaths of f, and t. converge, let join be the
first node on the t backpath that is also on the f backpath.
If the backpaths converge on a cycle and it the leaving arc pre
ceeds the join on the f, backpath, define join as the first
cycle node encountered on the f backpath. If the backpaths do
not converger join = <f> .
Several schemes are available for identifying the join
efficiently [6J. The depth (or number of successors, or pre
order distance) of nodes on the backpaths can be used to avoid
iterating either backpath past the join. Depth, the number of
nodes on the backpath until a cycle is encountered, can be used
to indicate which backpath node is deeper and should be iterated.
When both backpath nodes have matching depths, zero depths indi
cate that each backpath is on a root cycle. By remembering the
first root cycle node on each backpath, further iteration will
either reveal the root cycles to be distinct with join = $ , or
coincident with join defined as above. When both backpath nodes
have matching depths greater than zero, the nodes are compared for
26
equality. A match indicates the join, and a mismatch indicates
that both backpaths should be iterated tor another comparison.
If a join is encountered, the backpaths have merged and
either one can be used to complete the ratio test (GENNET
continues the t backpath ) . When a cycle is encountered the
q values are computed on the first pass around the cycle. On
the second pass around the cycle the q values are computed and
the ratio test is completed.
As the backpaths are iterated, the column transformation
is applied and the resulting terms of transformed column, Z ,
are used in the rat io test , seeking the minimum ratio:
MIN i
CP(k)
XU)
'9.
CP( IVAKU ) )XU )
 z
the capacity of the incoming arc,
for z > 0, node I,
for z < .
If a zero ratio is encountered during this process, the ratio
test may be preemptively terminated.
Step S3, Pivot
IF CP(k) is selected as the minimum ratio, then the enter
ing variable remains nonbasic and is reflected to its opposite
bound. Only the flows X( ) need be updated. To do this, the
backpaths are iterated again ana for each node I encountered,
X( ) is reduced by z x CP(k) .
27
If a basis exchange is required, an efficient update of
the basis representation must preserve the rooted cycle orien
tation, updating some entries in P( ) and D( ). Also, some
flows X( ), and some dual variables U( ), must be changed.
FAC ( ) must be established for nodes on newly created cycles.
Some bookkeeping in IVAR( ) and CP( ) may also be required.
The apparent intricacy of our task is deceiving. Careful
analysis yields an elegant solution. However, the supporting
arguments require close attention.
To simplify the explanation, reorient the incoming arc
(f, ,t.) to (i,j) or (j,i) (if necessary) so that the minimum
ratio is on the j backpath . Let the entering arc (i,j) have
the outgoing arc (c,d) on its jbackpath. Also, reorient the
outgoing arc (if necessary) so that the first node encountered
on the j backpath is c . Figure 2 shows a case for which
both reorientations are necessary.
In our example, arc 20, oriented from node 2 to node 11,
leaves the basis and arc 27, oriented from node 5 to node 13
enters. We call the backpath segment from j to arc (c,d) the
j  stem . In Figure 2, i, j, c, and d are shown. The jstem is
composed of nodes 5, 2, 3, and 11. The skeletal update:
a. Reverses the orientation of arcs within the
jstem; and
b. Urients the entering arc so that it precedes this
redirected path with the same orientation.
If the i and j backpaths merge, the node where they
merge is called the join. The join is node 3 in Figure 2.
28
If the leaving arc lies beyond the join on the backpaths
a new cycle is created in the basis exchange. In this case
the portion of the i backpath from node i to the node with
the join as its predecessor is called the istem. When node i
is on the j backpath the istem is null. In Figure 2, the
istem is node 13.
Figure 4 displays the pivot logic to be applied. The
algorithm visits each node affected by the basis update
exactly once . It proceeds up the jstem one node at a time
visiting the preorder successors of each stem node via IT( ).
If a join is encountered it switches to proceed up the istem
one node at a time and then returns to the jstem. At each
jstem node, the successors of the next lower stem node have
already been visited. The unvisited successors of the current
stem node can be divided into two groups: the left successors
are the nodes visited in preorder by iterating IT( ) from the
current stem node until the next lower stem node is encountered,
and the right successors of the stem node are the remaining
unvisited nodes reached by further iteration of IT( ). In Figure
2, nodes 8, 14, 12, and 7 are right successors of node 2 and
nodes 10, 13, 1, 6, 15, 9, and 4 are left successors of node 3.
As we climb the istem the traversal IT( ) is moditied so that
the last of the left successors (if any) points to the first of
the right successors and the last of the right successors (it
any) points to the previous stem node. As we climb the jstem,
the traversal is modified so that the last of the left succes
sors (if any) points to the first of the right successors and
29
f BITEH J
Set first
Jstem node
to visit.
Visit left successor
Figure 4. Pivot Traversal Scheme
30
the last of the right successors (if any) points to the next
node up the stem (because the update reverses predecessor
orientation for the jstem).
The immediate switch to the istem upon encountering the
join during the jstem iteration is motivated by a subtle
complication: while visiting the left and right successors
of the jstem nodes, the nodes on the istem and their succes
ors must be skipped if encountered. Because the istem nodes
are successors of the join, visiting the istem as soon as the
join is encountered (if one exists) on the jstem leaves us
with the preorder successor of the last istem node visited.
This valuable artifact enables the subsequent jstem iteration
to immediately skip all istem nodes and their successors should
they be encountered. This is the key step preserving an effi
cient onepass basis update. In Figure 2, istem node 13 and
its successor node 1 are successors of the join, node 3. The
preorder successor of the last istem node (called the preorder
link in Figure 4) is node b.
A stem node may have a right successor which is on the
root cycle (with depth zero). The preorder traversal array is
organized so that all successors of a cycle node are encountered
before the next cycle node. This implies that a cycle being
broken by a leaving arc will always be encountered as a right
successor of a stem node. In Figure 2, the broken cycle is
encountered as a right successor of node 2; if arc (2,11) were
not the leaving arc, then node 11 would be a preorder successor
of node 2.
31
The basic arc flows, X( ), are changed as each arc is
visited on the jstem, and (if a new cycle is created) on the
istem. If no cycle is created, X( ) is changed only it the
minimum ratio is nonzero, and then only on the arcs visited on
the backpaths.
During the update, the dual variables must be changed so
that
c k = u  m R u ,
k k
for every basic arc k oriented from node t to node f ,
K K
With incoming arc (i,j) (reoriented as in Figure 2 so that the
outgoing arc is on the jstem), this relationship is retained
for all nodes except for those which the update changes to be
successors of i: (i.e. the nodes on the jstem and their
successors ) .
If a cycle is not created, this update proceeds for each
jstem node and its successors as these nodes are visited in
preorder. for node s , and associated basic arc £ oriented
from s to p (s ) ,
U(s) = CU) + MULU) * U(P(s) ) ,
while the reverse orientation P(s) to s yields
U(s) = (CU)  U(P(s)))/(MULU)) .
32
As in pure networks, the preorder traversal assures that a value
of the dual variable of a predecessor node is always determined
prior to its use by any immediate successor nodes.
When a cycle is created, the dual variable must be deter
mined for one of the cycle nodes. Then, the dual variables of
the remaining cycle nodes and their descendents can be found
one at a time in preorder traversal.
This key dual variable is computed immediately after the
ratio test predicts creation of a new cycle (the leaving arc
lies beyond the join on the ratio backpaths). Consider the
current context for a new cycle:
rr
/ *
P(i)
P(j)
from which the new cycle will be formed (with modified pre
decessor function p ( ). ) :
/a p<p(j>>
rv rx
p(j)
^ — ^d , ., a „ v b ^ a ,, ^ b ,
p+1 d 3 b 2 a 2
 P
1
33
The corresponding neartrianyular system is:
(u p' u  P+ i
/ u_ 1 )
a b ,
p p + 1
p + 1
p
a_3 b_ 2
a 2 b l
= (c ,c
p  p +
i . 1 r.../C_ i )
where the indexing of c is understood to yield basis arc
costs (accomplished by indexing with IVAR( ) ).
The determination of one term (say, u_, ) of the solution
of this system is induced by modified forward substitution to
be (e .g . , [ 11] ) :
 U' , X — ,
1 ""I
where (the cycle factor) f is defined (again) as
b
f = 1
6=l
and u' is the corresponding term of the solution of the strictly
upper triangular system (omitting the cyclic coefficient b ,
p
and using forward substitution):
34
c
 p a p
i & 6 61 r , , ,
u; = for 6 = p+l,...,l .
o a „
Note that computation of u' requires that we traverse the
new cycle in a direction opposite to its predecessor orientation.
However, before the update creating the new cycle, the jstem
exhibits proper orientation for at least part of our work. Thus,
we can complete the first portion of the forward substitution
for u\ and accumulate the associated partial product component
of f while iterating the jstem before the update.
The remainder of the new cycle is accessed by iterating
the istem. As we proceed up the istem the remaining product
terms of f are accumulated, and the reverse i^tem path is
stored (e.g., using U( ) locations, which contain obsolete dual
values to be replaced during the imminent update). Reaching
the join, this stored reverse istem path is then accessed to
complete computation of u' .
The newly created cycle in Figure 5 is composed of jstem
nodes 5, 2, and 3, and istem node 13. The dual system becomes
~ u 13 + U 3 = 4b,6(J
u + u = lb .47
u  74u 5 = 26.76
88u + u = 20.67 ,
13 5
35
which yields
uj 3 = 19.0142,
f = 0,3488 (the new cycle factor), and
u,~  54.5132 (the new dual for node 13)
Thus, when a new cycle is to be formed, the new cycle nodes
must be visited once (after the ratio test and prior to the
pivotal update).
The onepass preorder traversal update can now proceed as
presented in Figure 4. The basis representation arrays are all
modified onthefly during this traversal. The update of nodes
on a newly created cycle (if any) includes establishing the new
cycle factor PAC ( ). Changes for P( ), D( ), IT( ), IVAR( ),
X( ), and U ( ) proceed analogously to the pure network case
(e.g., GNET [6]) with simple modification of generators for X( )
and U( ) to accommodate generalized network coefficients for
basic arcs.
Figure 5 shows the new basis (derived from the example in
Figure 2) before restoring neartriangulat ion with the update.
A new cycle is to be created and the new cycle factor and a dual
solution (for node 13 on the istem) are found at this stage.
Figure 6 displays the new basis restored to neartriangular
form. At this point, all basis representation arrays are updated
with the values shown in Figure 7 (data in italics has been
changed by the update ) .
36
Column
2 4 12 29 23 10 21 21 17 26 24 7 30 14 13
Row
2
5
8
14
12
7
11
3
10
13
1
6
15
11111
.74
.92
.98
1.18
i 1 !
i 1
!
!
1
1.06
1.17
111 111
1.07
:ti 1.0 J .83
1
.91
1.0
1.0 1.0
1
(The entering column is italicized. )
11 •< *//< • ///
OneTree
Figure 5.
New Basis Before Restoring NearTriangulation
(entering column 27, arc (5,13))
37
Column
4 12 29 23 10 2 17 7 30 14 13 21 26 24 27
Bow
2
8
14
12
7
3
10
6
IS
9
4
11
13
1
5
11111
.92
.98
1.18
1.06
1 1
1.0 1 1 1 1
1.07
.91
1.0
1.0 j
1 1
1.0
V
1
„ 1.17
1.0 .83 .88
1
1
A Preorder NearTriangulation
Figure 6. New Basis NearTriangulated
38
GENNET is designed to exploit intrinsic pure network struc
ture commonly found embedded in generalized network problems.
Note that when this algorithm is applied to pure network prob
lems, _i_t automatically adapts to a minor variant ot GNET. of
course/ GENNET uses floating point arithmetic operations which
are intrinsically slower on most computers than the pure additive
integer arithmetic of GNET (also, floating point arithmetic
requires some extra editing for mantissa truncation errors).
To mitigate this disadvantage, GENNET can test logically for
pure network arcs (with unit multipliers) and avoid unnecessary
floating point multiplication and division operations.
GENNET also employs an automatic dual basis aggregation
refinement ([6], p. 26 f f ) . Explicit values for D( ), U( ) and
IT( ) are maintained only for nodes with successors. An array,
A( ), records for each node the current number of its aggregated
successors . When an aggregated node is encountered in the
priceout, its dual is generated from that of the immediate
predecessor of the node. When a backpath ot an entering arc
begins with an aggregated node, it is disaggregated, and when the
leaving arc isolates nodes with no successors, they are
aggregated .
Figure 8 shows the arrays affected by the dual aggregation
scheme for the basis in Figures 2 and 3. IT( ) indicates aggre
gated nodes with (J entries, and these nodes have broken outlines
in the onetree depiction. The priceout of arc (5,1J) requires
that U(5) be generated using the predecessor dual U(2). Node b
subsequently starts the jbackpath and is disaggregated. The
update leaves node 11 with no successors, and thus aggregated.
39
Node Predecessor Depth Traversal Basic Variable Dual Cyc l e Fa ctor
P( )
D( )
IT( )
IVAR( )
X( )
U( )
FAC ( )
1
13
1
5
24
22.86U
17.026
*
2
5
8
4
3.883
6.557
0.3488
3
2
10
2
118.456
8.913
0.3488
4
9
2
lj,
13
O.U
35.173
*
5
U
2
.27
2.872
27.302
0.3488
6
3
1
11
7
21.308
48.388
*
7
2
1
3
10
3.434
77.192
*
8
2
1
14
12
27.087
16.634
*
9
3
1
4
14
9.380
38.633
*
10
3
1
6^
17
13.150
 9.330
*
11
3
2,
13
21
48.641
50.746
*
12
2
i
7
23
2.076
1.969
*
13
3
1
26
9.428
54.513
0.3488
14
2
i
12
29
22.204
11.834
*
15
3
i
9
20
16.550
76.533
*
Figure 7. GENNET Basis Representation Arrays
(for Basis in Figure 5)
40
Aggregated
Node
Depth
Traversal
Dual
Successors
D( )
IT(
)
U( )
A( )
1
2
3
47.148
5
3
U
13
31 .678
3
4
5
6
u
U
7
8
9
1
11
9.380
1
10
11
2
4.170
12
13
1
9
11.956
1
14
15
Aggregated OneTree \
^^^
Figure 8. Aggregated Basis Representation
(for Figures 2 and 3)
41
b. COMPUTATIONAL EXPERIENCE
Significant design alternatives tor GENNET have each been
evaluated by extensive experimentation at large scale. Illus
trative computational experience is abstracted in this section
for some of the prototype systems tested. Departing somewhat
from the style of the paper documenting such work for GNET lb],
relative performance is reported even lor some competitive design
features subsequently rejected tor adoption (some readers of [bj
have concluded, quite incorrectly, that only those teatures
reported tor GNET were tested). This should help other re
searchers avoid our mistakes, and may even change some widely
held misconceptions and correct a few translation errors in
textbooks .
Among the key issues to be resolved are:
a) Static Storage of Arcs . The arc lists can be stored
in arbitrary sequence, or, to save space, arcs can
be stored contiguously by tail node, or by head
node, thereby replacing an arclength index array by
a (presumably much shorter) hierarchical nodelength
entry point array.
b) Preorder Manipulation of Basis . The triple label (aug
mented predecessor index) method [zu,22\ will be
presented and compared with the preorder traversal
method .
c) basis Aggregation . An aggregated basis representation
will compete with an explicit representation.
42
d ) i^lci n y Sch emes . Candidate list schemes and explicit
arc pricing mechanisms widely used in general linear
programming systems will vie with dynamic candidate
queue disciplines.
e) Pure Network Speci alization . Generalized network
algorithms would ideally adapt to pure networks with
efficiency comparable to pure network codes.
t ■) Star tin g , Tunin g and Tai lor ing . Which algorithm
parameters and settings lead to high efficiency tor
interesting classes of problems? Are heuristics tor
advanced starting solutions worthwhile?
^ ) Generali za tions. Advanced teatures and generalizations
will be suggested.
Computational tests have been made with many problems,
including a benchmark suite ot pure network problems generated
with NETGEN [28J, and generalized network problems generated
by NETGENG [17,1»J. figure y gives some problem characteristics
Static arc storage has been implemented in three ways:
Contiguous by head node with hierarchical node
length entry point array,
Contiguous by tail node, with hierarchical node
length entry point array, and
Explicit arcs in arbitrary order.
In competition with our basis manipulation using preorder
traversal, a triple label representation originally suggested
by h'. Johnson [2bJ has been implemented tor pure networks and
called the augmented predecessor indexing method by Glover,
Karney, and Klingman [2UJ. Glover, Klingman ana stutz 122J
43
Percent
Problem
Nodes
Sources
S inks
Arcs
Capacitated
NETGEN
(Pure )
NG15
4UU
200
200
4,500
NG18
400
8
60
1,306
20
NGly
400
8
bO
2,443
20
NG2 2
400
8
60
1,416
40
NG2 3
400
8
60
2,836
40
NG26
400
4
12
1,382
80
NG27*
400
4
12
2,676
80
NG28
1,000
50
50
2,yoo
NG29
1,000
bO
50
3,400
NG30
1,000
50
50
4,400
NG31
1,000
50
bO
4,800
NG3 2
1,500
75
75
4,342
NG33
l,b00
75
75
4,385
NG34
1,500
75
75
5,107
NG3b
1,500
75
75
5,730
NETGENG
(Generalized )
GTU1
200
100
100
1,500
GTU2
200
100
100
2,000
100
GTU7
300
135
115
4,000
GT12
400
20
100
5,000
GT 1 5
1,000
5
yy5
4,000
100
GTlb
1 ,000
20
100
6,000
100
GT 1 8
1,000
30
400
7,000
Figure y. bpme Benchmark Problems
(Problem NG27 is extensively studied in [6J
44
report that the method has been extended to generalized networks,
but reveal no details.
We have implemented our own elticient version of the triple
label scheme.
The triple label representation uses predecessor, successor,
and brother pointers lor each node. Figure 1U shows these arrays
lor the basis in Figure 2.
To briefly illustrate the triple label scheme tor gener
alized networks, let our situation be the same as tor the pre
order example (the jbackpath of the incoming arc is arranged
to include the outgoing arc and to encounter node c first on
that backpath). Let
V d+1 = X '
and the backpath from j to c
v d' V d1 C
The skeletal update scheme is
45
Node Predecessor successor brother
P( )
S( )
b( )
1
13
u
2
3
11
10
3
11
2
4
9
U
5
2
8
6
3
o
lb
7
2
u
8
2
u
14
9
3
4
10
3
U
13
11
2
3
b
12
2
U
7
13
3
1
b
14
2
u
12
15
3
u
9
Figure lu. Triple Label Basis Representation
( for t' igure 2 )
46
1. Set 6 = d
2. It s ( v 6 _^) = v 6 ' ^oto Step J
Otherwise, it possible, tind a node v*
such that P(v*) = v
61
and B( v* ) = v r ,
— — > — o
and set B(v*) «■ b(v ), Go to Step 4
3. Set b (v (5 _ 1 ) + B(v 6 ) ,
4. Set P(v 6 ) ♦ v 6+1 ,
B <V * S(v 6 + 1 } '
b. Set 6 <■ 61,
Then, it v x + i * c, Go to ^tep_ 2,
Otherwise, Stop .
(Step 2 exhibits the key extension tor generalized networks of
the pure network triple label scheme.)
These tive steps reverse the orientation ot all arcs on
the jstem and orient ( v ^ + _i' v h) so that it beyins this redirected
path. All other triple label operations are obvious alterations
of the preorder traversal procedure.
A static cand idate list pricing strateyy (e.g., [I7,la,jl]))
an explic it arc pricing method reminiscent ot yeneral linear
proyraioming systems, and a dynamic candi date queue lb] have been
tested.
The (L,,L.J candidate list procedure is a simple strategy.
Nodes with leaving arcs (or entering arcs for contiguous head
node arc lists) are sequentially priced, placing the most nega
tive candidate (it any) trom each node on the candidate list
47
until L,. candidates have been located (arbitrarily organized arc
lists require explicit arc pricing). Entering arcs are chosen
trom the candidate list by most negative reduced cost until L,
iterations have been carried out/ or until all list entries have
nonnegative reduced costs. Arcs with nonnegative reduced costs
are dropped from the list and replaced by continuing to scan the
nodes until L.. candidates have been tound. It an exhaustive pass
through the nodes results in less than L candidates, then an
optional closing gambit sets L equal to the actual candidates
found/ and reduces L, by halt unless L, equals one. Glover/
Hultz, Klingman and Stutz [ 1 7 , 1 8 J report (L,,L y ) ot (b,lU) to be
best in their work.
The candidate queue is a dynamic list ot interesting arcs
and nodes, scanned in a cyclic manner. The entering arc is
selected from the queue by pricing nne entries; if an interesting
node is encountered it is replaced by its bestpriced entering
arc (or leaving arc tor contiguous tail node arc lists). Arcs
pricing favorably are retained in the queue. When the end of
queue is encountered/ the queue is refreshed by pricing 1PG nodes
in a cyclic general arc scan. During an opening gambit ot nns
pivots, the nodes incident to the entering basic arc are added to
the queue. There is no closing gambit, since the queue automa
tically shrinks and finally collapses at optimality. Bradley,
brown, and Graves 16J suggest WNhi = 62, NNh = 3m/4 and
1PG = m/lU + 1 for pure network problems with m nodes.
A rule to break ties in the ratio test which guarantees
finite convergence for pure transshipment problems has been
48
developed by Cunningham [12]. Bradley, Brown and Graves 16]
show that the conditions necessary for finite convergence are
naturally satisfied by GNET on over yu% of its degenerate pivots.
Elam, Glover and Klingman lib] have observed that the results of
Cunningham can only be extended to the generalized network case
when the multipliers are positive. We have not used Cunningham's
modif ication .
Bland [4] presents a class ot restrictions of pricing and
ratio tests for general linear programs which relies exclusively
on primal simplex representation and guarantees finite conver
gence. These rules are easily modified to produce an efticient
finite simplex algorithm. The modification interferes with ef
fective pricing strategies only during degenerate pivot sequences,
and the restrictions increase in severity only with the number of
pivots in that sequence. However, during a degenerate pivot se
quence restriction records must be accumulated (e.g., a list with
each incoming variable in one ot our schemes ) . This record is
naturally accommodated by the dynamic candidate queue, but not by
a static candidate list or explicit pricing. No purpose is
served by reporting such unbalanced competition.
A starting strategy has also been tested in conjunction with
pricing alternatives. A straightforward starting method ex
amines each node with supply (or demand tor contiguous arc stor
age by head node) and assigns as much flow as possible to its
least cost leaving (entering) arc. The procedure stops when an
exhaustive pass of the nodes makes no additional flow assignments.
49
The starting solution achieved is not necessarily leasible.
(F.g., "exhaustive pass sequential source minimum start" [Its].)
Artificial arcs are driven from the basis in all experiments
using a bigM method (e.g., [b]). This choice is principally
motivated by the comparability of competitive tests between pure
and generalized network codes on pure and generalized network
problems. (A twophase method is employed in production use.)
Choosing the best bigM value is a bit tricky. The smallest
bigM value which yields a feasible optimal solution (if one
exists) is best in our experience. Small bigM values may tail
to produce feasibility, and large values inflict numerical
difficulties. In practice, a default value is used and an
automatic restart recovery is applied it an mteasible solution
persists. If a restart with a higher bigM value tails to
reduce the total inf eas ibility , a terminally inteasible solution
is declared. Figures 11 and 12 indicate the multiple ot maximum
absolute arc cost used for bigM in each problem.
Computational tests have been performed on various computer
systems. The times reported here are accurate to the precision
displayed tor IbM 37u/lbb3 using the FORTRAN H compiler with
OPT(z). Solution times exclude input/output overhead. Ch'NNtT
uses double precision (IbM RhJAL*b) arithmetic for floating point
operations and storage.
solution times are given in Figure 11 for the pure network
test problems. Performance is given tor three pure network codes
(two versions ot GNfcT and SUPFkk) as well as tor several repre
sentative generalized network prototype systems. we can thus
50
compare the best generalized network scheme with the best pure
network code exhibiting equivalent features (GNfcT, or its
aggregated successor variant [6J).
The times for SUPEKK also provide the only available objec
tive means lor comparison of our implementations to that of
Glover, Hultz, Klingman and btutz [14]; they report that their
generalized network code, N£TG, is about as fast as stiPfcKK (a
fast outotkilter code for pure networks lij) when both are used
to solve pure networks. Using their version of SUPtKK on our
computer we have shown that our implementation of NETG (called
TLA in our nomenclature) is at least as efficient as their claims
for NfcTG.
51
^
un
3
X>
f
^H
00
r
oo
CN
00
r»
CN
n
^r
CN
r
*
—i
oo
oo
JO
.— 1
OO
rH
in
^r
JO
^
00
oo
00
r>
00
a
a<
."N
rH
(N
ri
Ox)
.—1
^r
^r
in
n
r»
X>
X
oo
^r
^
£>
co
a
CD
■o
O
:;
00
r
oo
vO
30
oo
o
P~
xO
3
jo
oo
oo
OO
■=T
3
oo
H
II
><
1— 1
oo
JO
00
■^
00
"*
m
<=r
*=}<
JO
cn
JO
xj>
3
r
*
aJ
a
a
u
Z
z
.>
—1
i— 1
rH
— i
f— 1
cn
N
CN
oo
00
o
'J
z
x:
rH
<D
Z
£>
<<
r
om
r^
00
00
VO
00
rH
^H
r
oo
X>
—1
=*
r
r
CD
H
II
oo
^
KD
<tf
«tf
00
^
>r
JO
■JS
sD
•JO
JO
00
r
oo
u
a
a
a,
3
2
z
m
rH
r— t
f— 1
— i
H
cn
•N
r*i
N
H
X
3
z
33
CN
■M
Li
fO
to
■30
II
a
z
z
CN
OO
Ox)
00
II
a
z
z
.M
00
II
a
z
z
g
I
Oil
X
 <
in a
g
<L>
z
rH
a
.Q
:o
H
Li
a
Oi
z
in jo o o
r\ CN OM OM
mouOLDOnnon
H CN H M ,M H H M M
UO JO
r
^
3
x>
^H
JO
00
r^
OO
o
OO
CN
00
oo
o
— 1
o
•<*
r^
t
r»
■xf
JO
xO
00
oo
JO
i— I
=tf
JO
00
00
N
rH
H
rx)
Ox]
CO
oO
OO
oo
r
CN
o
00
00
^
OO
CN
rH
00
v£)
r~
r
OS)
JO
r
00
X
m
v£>
r^
<£>
xO
m
r
cH
00
OM
OJ
■n
<—\
■*
JO
Jl
CN
OJ
rH
Osl
.N
00
~n
00
00
oo
OJ
On)
o
00
o
r~
Nf
^r
00
r\
OJ
o
3
og
x>
00
r~
r
rH
00
oo
m
00
JO
r
r
f—l
o
^r
^r
tt
00
v£>
00
00
OM
00
oo
00
^r
^r
^r
n
oo
.^0
r
O
O
rH
UO
oo
^r
3
OnI
30
CO
OnI
00
^
,00
r^
rH
VO
r— 1
sO
r
^r
r~
NI
,00
JO
JO
00
r{
On)
30
r
.N
rH
OM
Osl
og
OJ
00
^r
^r
.00
iH
.00
00
oo
oo
f—t
r
o
oo
rH
CN
xO
N
'X>
00
oo
CN
oo
OO
1— 1
oo
r~
oo
vD
3
rH
>^
00
in
^3"
r~
00
CN
r\
30
JO
Ov!
r<
rt
rH
rH
"*
JO
^r
JO
00
oo
00
3
00
• •
to
c
JO
00
oo
CN
00
liO
r
OO
oo
3
rH
og
OO
^
JO
c
CO
rt
rt
rH
Osl
OS]
CN
CN
CN
CN
.00
OO
OO
OO
.00
00
3h
■3
'■J
'J)
'J
^J
a
'■J
■J)
'J
'J
:d
■~J
:d
:•)
CJ5
o
Z
z
z
Z
z
z
z
z
z
z
z
z,
z
z,
Z
to
u
<D
>
(0
g
u
U)
■iJ
CO
c
•H
g
c
u
CD
•H
fO
o
rH
4J
x:
o
CO
A
fO
o
Li
l
N
<D
u
•rl
e
CD
CO
%
c
r^
CO
<T3
ai
31
0)
4>
31
c
N.
o
CO
Vj
•fi
rt
o
<D
u
Q)
3
H
•H
A
CO
U
tl
(0
^:
iJ
a
r{
TD
Li
fD
CD
CD
CD
4J
5
rH
3
rH
<T3
jJ
•H
CD
04
Ol
CD
<n
3.
•H
CD
Z
Hi
o<
u
U
\
\
+J
Ji
CD
■a
JJ
rji
Li
rO
ID
M
fC
3
fl)
•H
rV
:u
XI
J
<C
XI
• •
•
"O
—1
c
Q)
CD
3
Li
CD
3
J
01
s
I
en
■h
r>
in
in
j~)
in
H
x>
■^
<T\
x>
r
*&
ro
rM
lO
a2
rH
X
H
<T\
lD
r~
rH
30
[»
rH
Z
II
Ol
2
u
o
cn
ro
rsi
ro
n
CTi
30
u
z
X
cm
o
z
CN
o
r
CN
CN
Y
r
00
ro
3
i— i
00
3
<J\
r
sf
rH
II
a<
a
3
CM
«*
ro
r
in
3
^r
2
X
i— 1
ro
CN
ro
II
W
z
m
33
4J
CN
Ll
CO
CN
fO
II
<
•_n
■U
a
3
w
z
X
rH
CN
00
II <
M O
Z H
Z
VD
ro
3
x>
.
■0
7i
.•o
r>
Li":
=*
Xl
ro
=*
LD
r~
rH
P~
CT>
r
«*
00
3
VO
CN
o
ro
50
Ti
CO
rH
rH
ro
o
IT)
CN
rH
J'.
?
 tf
r
"=1"
iH
<
x>
.—1
CTi
in
H
00
rH
^r
».
ij
•
LO
EH
rH
f
N
^r
t
N
rH
CT\
rH
<3<
ro
X
r
ro
rH
23
rH
x>
00
t,
kO
r
•^r
r~
3
=*
3
00
CO
CN
x>
;■
O
N
•
rH
3
•~n
X>
3
o
=r
37>
r
o
^t*
3
00
3
ro
..
J*
X
ro
CN
ro
ro
CO
CN
r
rH
CN
X>
N
ro
j
X)
c
H
c
ro
■H
■n
•U
U
■"
OJ
N
>
•H
.
c
e
u
re
CO
4J
rj)
• H
Li
c
Li
ro
CD
£
a
Cfl
'J
U
Li
Li
Li
03
O
CO
E
03
w
Li
C/3
+J
cu
03
•H
c
L)
"
■ H
—
U
•H
;
3
H
•H
jQ
W
a
L
:
X
a
r 1
a
Ml
'.
\
03
03
jj
J.
3
rH
rO
■H
03
3,
•j]
ro
3
Hi
Ol
Li
S.
X
\
I)
L^
o
iJ
rji
•
M
ro
m
T
xl
<l
XI
• e
73
.
'
rji
03
J
1)
H
~
L
a<
.0
03
H
'3
''
C
V
c
Z
N
03
: 
3
4J
Li
ro
4J
W3
uO
00
lO
o
rN
rH
ro
rH
X>
^r
m
ro
.>..'
^r
J>
r
<*
rH
CO
N
o
ro
Ti
N
rH
r
^
lO
c
'J
03
Z
r 1
M
.a
'J)
H
M
M
Q,
z
CM
r
rH
N
f)
X
3
3
rH
ri
rH
H
rH
H
rH
H
H
^1
H
Eh
C3
CJ
;
^
r
J
J
'jo
.•
'TO
c
c
ro
r:
o
03
j"
53
However, in these tests TLA is substantially outperformed by
the alternate systems. For the pure network problems, best
performance is achieved by (Figure 11):
Contiguous arcs by head node,
Candidate queue pricing,
Preorder traversal, and
Aggregated successors.
TLA does not incorporate any of these features, and is generally
less than half as fast as competitors.
Although GENNET (HgPX) should in theory rival GNET (HyPX)
with pure network problems, the overhead of testing in GENNET
for more general basis structure and the additional computa
tional burden of floating point arithmetic exact a performance
penalty of about 15 percent.
Figure 12 shows solution times for the generalized trans
shipment network problems. Note that the starting strategy helps
candidate list performance and hinders the candidate queue.
Arranging arcs contiguously by head node dominates both tail
node and explicit arc list designs. The candidate queue pro
vides good performance _if_ accompanied with contiguous arcs by
head node. Preorder traversal continues to provide better
performance than triple label representation in all design
contexts. Aggregated successors offer a pronounced advantage.
GENNET (HyPX) provides best overall performance. It
offers a decided advantage on problems with many more sinks
than sources, a situation common in real life.
54
Figure 13 displays performance of GENNET(GN, HPQX) applied
to a set of (GN) problems extracted from a collection of real
world LP/MIP models [1UJ. Despite the slight additional floating
point arithmetic required to solve (GN), GENNET solves these
problems much faster than would be predicted by experience with
randomly generated GT problems. Tuning of the pricing mechanism
greatly enhances this difference.
Problem
Node;
Arcs
Seconds
Pivots
AIRLP
17U
3,040
2.62
420
CUAL
170
3,923
1.80
471
STEEL
422
1,279
.39
499
FOAM
951
4,953
3.74
1,258
ODSAS(GN)
1,431
4,615
3.22
1,427
ALUMINUM(GN)
2,178
7,216
3.57
2,794
REFINE (GN)
3,110
6,617
4.72
3,322
FOOD(GN)
3,716
13,907
12.11
7,004
(BigM = 10 x largest cost coefficient)
Figure 13. (GN) Test Problems
(GN rows extracted from realworld LP/MIP models [10
with null columns deleted and slack arcs added.)
55
Close scrutiny of solution trajectories lends some insight
into GENNET's good performance. GENNET has a onepass itera
tion unless a cycle is formed; a cycle is formed on only bto24
percent of all iterations for these problem sets — 5tolU percent
for most problems. Also, the explicit (nonaggregated) subset of
the nodes is remarkably small, seldom numbering much more than
the number of source nodes. Finally, the length of backpaths is
quite short, averaging about the number of echelons (path length
from sources to sinks) in the model, or just more than 2 in these
problems .
56
CONCLUSION
The generalized network, system GENNh'T is small, fast and
easy to modify. Adaptations have already included using GENNfcT
in a system to solve generalized networks with complicating side
constraints an/or complicating variables (Mcbride [3UJ). GENNET
has also been incorporated in a powerful microcomputerbased
network optimization system by Brown, Duff and t'inley [7,lbJ
using an APPLEII host and PASCAL implementation language.
Modifications for mixed integer generalized networks have also
been tested (though not with care sufficient to warrant
publication at this time). GENNET has proven to be a worthy
successor of GNET [6].
Preorder traversal is appealing for its mathematical and
implementation elegance, and has proven to be efficient and
flexible for generalized networks (as it was tor pure networks).
(Adolphson and Heum [1] have also suspected this and have in
dependently pursued this avenue.)
Experience shows that the GENNET design pertorms much more
efficiently on real models than on randomly generated test
problems of nominally equivalent size; this design is also tech
nically and philosophically compatible with the various systems
we have devised tor solviny other more general classes ot
optimization models.
b7
The EQRTRAN programs GENNET — (GT) and (GN) versions —
(Copyright 1984) are licensed to researchers lor a nominal
charge on an exclusive use basis. For further information write
the authors via P.O. Box 1832, Alexandria, Virginia, 22313, USA.
5b
7. ACKNOWLEDGMENTS
Gordon Bradley and Glenn Graves have always olfered us
complete support in our work: we gratefully acknowledge their
help and encouragement. Rick Rosenthal contributed many valu
able suggestions to clarify the presentation. John Tomlin has
discovered some subtle imprecisions in our description.
Kevin Wood has taught from early manuscripts and suffered their
shortcomings nobly.
by
REFERENCES
1. Adolphson, D. and Heum, L., "Computational Experiments on
a Threaded Index Generalized Network Code," presented at
the Houston URSA/TIMS Meeting, October 14, 1981.
2. Balachandran , V., "An Integer Generalized Transportation
Model for Optimal Job Assignment in Computer Networks,"
Operations Research , Vol, 24, No. 4 (1976), pp. 742759.
3. Barr, R., Glover, F., and Klingman, D., "An Improved
Version of the OutofKilter Method and a Comparative
Study of Computer Codes," Mathematical Programming ,
Vol. 7, No. 1 (1974), pp. 6087.
4. Bland, R., "New Finite Pivoting Rules for the Simplex
Method," Mathematics of Operations Research , Vol. 2, No. 2
(1977), pp. 1U31U7.
5. Bradley, G., "Survey of Deterministic Networks," AIIE
Transactions , Vol. 7, No. 3 (1975), pp. 222234.
6. , Brown, G., and Graves, G., "Design and Implemen
tation of Large Scale Primal Transshipment Algorithms,"
Management Science , Vol. 24 (1977), No. 1, pp. 134.
7. Brown, G., Duff, R., and Finley, M., "Design and Demonstra
tion of a MicrocomputerBased Network Optimization System,"
presented and demonstrated at the Detroit ORSA/TIMS Meeting,
April 19, 1982.
8. , and Graves, G., "Design and Implementation of a
Large Scale (Mixed Integer, Nonlinear) Optimization
System, " paper presented at the Las Vegas ORSA/TIMS
Meeting, November 1975.
9. , and McBride, R., "Exploiting LargeScale Networks
with Gains," paper presented at the Houston ORSA/TIMS
Meeting, October 14, 1981.
10. , , and Wood, K., "Extracting Embedded
Generalized Networks from Linear Programming Problems,"
Technical Report, University of Southern California,
August 1983.
11. , and Wright, W. , "Automatic Identification of
Embedded Network Rows in Largescale Optimization Models,"
Mathematical Programming ( to appear ) .
12. Cunningham, W., "A Network simplex Method," Mathematical
Programming , Vol. II, No. 2 (1976), pp. 1U5116.
13. Dantzig, G., Linear Programming and Extensions , Princeton
University Press, Princeton, New Jersey, 1963.
60
14. Eisemann, D., "The Generalized Stepping Stone Method tor
the Machine Loading Model," Man agement S c ienc e, Vol. 11,
No. 1 (1964), pp. 154177.
15. Elam, J., Glover, F., and Klingman, D., "A Strongly Con
vergent Primal Simplex Algorithm for Generalized Networks,'
Mat h ematic s of Operations Resear ch, Vol. 4, No. 1 (1979),
pp." 3959.
16. b'inley, M., "An Extended Microcomputerbased Network
Optimization Package," MS Thesis, Naval Postgraduate
School, Monterey, September 1982.
17. Glover, F., Hultz, J., Klingman, D., and Stutz, J., "A New
Computerbased Planning Tool," Research Report CCS 289,
Center for Cybernetic Studies, University of Texas at
Austin, 1977.
18. , , , and , "Generalized Networks:
A Fundamental Computerbased Planning Tool," M anag e ment
Science , Vol. 24, No. 12 (1978), pp. 12U9122U.
19. ^, Klingman, D. and Stutz, J., "Augmented Threaded
Index Method tor Network optimization," IN FO R, Vol. 12,
No. 3 (1974), p. 293298.
20. , Karney, D., and Klingman, U., "The Augmented
Predecessor Index Method for Locating Stepping Stone Paths
and Assigning Dual Prices in Distribution Problems,"
Transportation Science , Vol. 6, No. 2 (1972), pp. 171179.
21. , and Klingman, D., "A Note on Computational
Simplifications in Solving Generalized Transportation
Problems," Tran sport ation Science , Vol. ~! , No. 4 (1973),
pp. 351361.
22. , , and Stutz, J., "Extensions of the Aug
mented Predecessor Index Method to Generalized Network
Problems," Transportation Science , Vol. 7, No. 4 (19 7 3),
pp. 377384.
23. Jensen, P. and barnes, J., Network Flo w Pr ogramming ,
John Wiley and Sons, New York, 198U.
24. , and bhaumik, G., "A Flow Augmentation Approach to
the Network With Gains Minimum Cost Flow Problem,"
Man a gement Science , Vol. 23, No. 6 (1977), pp. 63164J.
25. Jewell, w., "uptimal Flow Through Networks with Gains,"
Operation s Research , Vol. 1U (1962), pp. 4' 7 6499.
26. Johnson, E., "Networks and Basic Solutions," Operations
Research, Vol. 14, No. 4 (1966), pp. 619623.
61
27. Kenninyton, J., and Helgason, R., Algorithms t or Ne twor k
Progr amming , John Wiley & sons, New York, 1980.
28. Klingman, D., Napier, A., and Stutz, J., "Nh'TGFN — A Program
for Generating Large Scale (Un) Capacitated Assignment,
Transportation, and Minimum Cost Flow Network Problems,"
Manag e me nt Science , Vol. 20, No. 5 (1974), pp. 814821.
29. Maurras, J., "Optimization of the Flow Through Networks
with Gains," Mathematical Programmin g, Vol. 3 (1972),
pp. 13S144.
30. McBride, R. , "Solving Embedded Generalized Network
Problems," Working Paper, School of Business
Administration, University of Southern California,
April 1981.
31. Mulvey, J., "Pivot Strategies for PrimalSimplex Network
Codes," Journal of the Association t or C o mp ut ing Machinery,
Vol. 25 (1978), p. 266270.
62
DISTRIBUTION LIST
NO. OF COPIES
Library, Code 0142 2
Naval Postgraduate School
Monterey, CA 93940
Dean of Research 1
Code 012A
Naval Postgraduate Schoo
Monterey, CA 93940
Library, Code 5b 1
Naval Postgraduate School
Monterey, CA 93940
Professor G. G. Brown 60
Code b5Bw
Naval Postgraduate School
Monterey, CA 9394U
Defense Technical Information Center 2
Cameron Station
Alexandria, VA 22314
63
DUDLEY KNOX LIBRARY
3 2768 00347374 5