94
3. A Procedure for Solving the Optimal Expansion
Problem
if the state of each arc remains unchanged after continued adjustment of
the TC values, a feasible solution cannot be found and the algorithm terminates. An indication for termination occurs if D f = oo at nonbreakthrough.
3.3J. Summary
of the Out-of-Kilter
Algorithm
The five principal steps of the OKA may be summarized as follows.
Initial Conditions. Start with a circulation that conserves flow and any
set of 7Γ values.
Step 1. Find an out-of-kilter arc (i, j). If none, stop. The optimal solution has been found.
Step 2. Determine whether the flow in the arc should be increased or
decreased to bring the arc into kilter. If it should be increased, go to step 3;
if it should be decreased, go to step 4.
Step 3. Find a path in the network, using the labeling algorithm, from
j to i along which the flow can be increased without causing any arc on the
path to become (more) out of kilter. If a path is found, increase the flow in
the path and also in (t, j). If (t, j) is now in kilter, go to step 1. If it is
still out of kilter, repeat step 3. If no path can be found, go to step 5.
Step 4. Find a path from i to j along which the flow can be increased
without causing any arc to become (more) out of kilter. If a path is found,
increase the flow in the path and decrease the flow in (t, j). If {i } j) is now
in kilter, go to step 1. If (i, j) is still out of kilter, repeat step 4. If no path
is found, go to step 5.
Step δ. Change the τ values and repeat step 2 for arc (i, j), keeping the
same labels on all nodes already labeled. If the node numbers become infinite, stop; there is no feasible solution.
3.3.8. Example of Application
of the OKA
Figure 3.11 shows a minimum-cost circulation problem that is solved by
the OKA. The ordered triple
wy, — &*;) is shown on each arc. The
original arc flows and node number (ic values) appear as underlined numbers. For example, fa = 2 and η = 0. As initial conditions choose η = 0
for i = 1, 2, 3, 4 and fa = fa = fa = fa = 2 with fa = fa = fa = 0.
Note that conservation of flow occurs at every node.
The OKA determines the flow in every arc that gives the minimum-cost
circulation. Seven iterations are necessary to obtain the optimal solution;
calculations are detailed in the following pages. Figure 3.13 shows
3. A Procedure for Solving the Optimal Expansion
Problem
if the state of each arc remains unchanged after continued adjustment of
the TC values, a feasible solution cannot be found and the algorithm terminates. An indication for termination occurs if D f = oo at nonbreakthrough.
3.3J. Summary
of the Out-of-Kilter
Algorithm
The five principal steps of the OKA may be summarized as follows.
Initial Conditions. Start with a circulation that conserves flow and any
set of 7Γ values.
Step 1. Find an out-of-kilter arc (i, j). If none, stop. The optimal solution has been found.
Step 2. Determine whether the flow in the arc should be increased or
decreased to bring the arc into kilter. If it should be increased, go to step 3;
if it should be decreased, go to step 4.
Step 3. Find a path in the network, using the labeling algorithm, from
j to i along which the flow can be increased without causing any arc on the
path to become (more) out of kilter. If a path is found, increase the flow in
the path and also in (t, j). If (t, j) is now in kilter, go to step 1. If it is
still out of kilter, repeat step 3. If no path can be found, go to step 5.
Step 4. Find a path from i to j along which the flow can be increased
without causing any arc to become (more) out of kilter. If a path is found,
increase the flow in the path and decrease the flow in (t, j). If {i } j) is now
in kilter, go to step 1. If (i, j) is still out of kilter, repeat step 4. If no path
is found, go to step 5.
Step δ. Change the τ values and repeat step 2 for arc (i, j), keeping the
same labels on all nodes already labeled. If the node numbers become infinite, stop; there is no feasible solution.
3.3.8. Example of Application
of the OKA
Figure 3.11 shows a minimum-cost circulation problem that is solved by
the OKA. The ordered triple
wy, — &*;) is shown on each arc. The
original arc flows and node number (ic values) appear as underlined numbers. For example, fa = 2 and η = 0. As initial conditions choose η = 0
for i = 1, 2, 3, 4 and fa = fa = fa = fa = 2 with fa = fa = fa = 0.
Note that conservation of flow occurs at every node.
The OKA determines the flow in every arc that gives the minimum-cost
circulation. Seven iterations are necessary to obtain the optimal solution;
calculations are detailed in the following pages. Figure 3.13 shows