3.3. The Operational
Policy Problem (Problem
III)
93
given labeled node is marked scanned. Now choose a labeled, unscanned
node χ and repeat the above procedure, attempting to label each node that
forms an arc incident to node x. Continue choosing and labeling nodes until
j is labeled. If node j is labeled, a flow-augmenting path has been found and
the flow in the connecting cycle is changed according to the label value.
Now arc (i, j) is either in kilter or less out of kilter. Pick an out-of-kilter
arc and repeat the procedure.
3.3.6.
Nonbreakthrough
However, it is not always possible to pick a flow-augmenting path because the algorithm avoids those arcs for which a change in flow will cause
the arc to become (more) out of kilter. In this case, the path would halt
at a labeled, scanned node from which no unscanned node could be labeled
because of the state of each connecting arc Such an event is designated as
nonbreakthrough. The impasse may sometimes be resolved by changing the
state of some arc(s). The state of arc (i } j) is uniquely determined by
Qtj
=
^ry
b%j, and the π values (unrestricted dual variables) may
be changed without affecting feasibility. At nonbreakthrough there are
two sets of mutually exclusive nodes: labeled nodes and unlabeled nodes.
The only π values of interest are those that will change the state of arc(s)
connecting labeled and unlabeled nodes so that the path may be extended
and possibly conpleted. Let X be the set of labeled nodes and X be the set
of unlabeled nodes. Let Μ be the set of arc(s) (i, j) originating at a node
belonging to X, terminating at a node belonging to X, and having the
property that q^ is positive and fa is less than or equal to its upper bound.
Let Μ be the set of arc(s) (t, j) originating in X terminating in X } with
Qij negative and /*/ greater than or equal to its lower bound.
Thus
Μ =
i € X } j 6 X, qu > 0, /„ < η ν
Μ =
ιζΧ,
jex,
qij<0,
fu>lu
Let
D = min [qu}, D = min {— Μ
Μ
Change the node numbers (π values) of each node in X by adding D f to
Ti for each i £ X, and recompute the state of each arc connecting a node
in X to a node in X. If the state of at least one arc is changed, return to the
labeling procedure. If by this process the desired node is labeled, the flow
is changed according to the label. All labels are then eliminated, another
out-of-kilter arc is chosen, and the operation begins once again. However,
Policy Problem (Problem
III)
93
given labeled node is marked scanned. Now choose a labeled, unscanned
node χ and repeat the above procedure, attempting to label each node that
forms an arc incident to node x. Continue choosing and labeling nodes until
j is labeled. If node j is labeled, a flow-augmenting path has been found and
the flow in the connecting cycle is changed according to the label value.
Now arc (i, j) is either in kilter or less out of kilter. Pick an out-of-kilter
arc and repeat the procedure.
3.3.6.
Nonbreakthrough
However, it is not always possible to pick a flow-augmenting path because the algorithm avoids those arcs for which a change in flow will cause
the arc to become (more) out of kilter. In this case, the path would halt
at a labeled, scanned node from which no unscanned node could be labeled
because of the state of each connecting arc Such an event is designated as
nonbreakthrough. The impasse may sometimes be resolved by changing the
state of some arc(s). The state of arc (i } j) is uniquely determined by
Qtj
=
^ry
b%j, and the π values (unrestricted dual variables) may
be changed without affecting feasibility. At nonbreakthrough there are
two sets of mutually exclusive nodes: labeled nodes and unlabeled nodes.
The only π values of interest are those that will change the state of arc(s)
connecting labeled and unlabeled nodes so that the path may be extended
and possibly conpleted. Let X be the set of labeled nodes and X be the set
of unlabeled nodes. Let Μ be the set of arc(s) (i, j) originating at a node
belonging to X, terminating at a node belonging to X, and having the
property that q^ is positive and fa is less than or equal to its upper bound.
Let Μ be the set of arc(s) (t, j) originating in X terminating in X } with
Qij negative and /*/ greater than or equal to its lower bound.
Thus
Μ =
i € X } j 6 X, qu > 0, /„ < η ν
Μ =
ιζΧ,
jex,
qij<0,
fu>lu
Let
D = min [qu}, D = min {— Μ
Μ
Change the node numbers (π values) of each node in X by adding D f to
Ti for each i £ X, and recompute the state of each arc connecting a node
in X to a node in X. If the state of at least one arc is changed, return to the
labeling procedure. If by this process the desired node is labeled, the flow
is changed according to the label. All labels are then eliminated, another
out-of-kilter arc is chosen, and the operation begins once again. However,