procedure for a blocking factor remains effective as the IDM expands,

the solution procedure is said to "extend."

Theorem 3-6: Call a block with blocking factor equal to k a k-group.

For the solution of k-groups in ascending order the following condition

is necessary and sufficient for extension of a solution procedure. The

decision variables offset from U. must all be k greater than tear

variables within the last k-group. An analogous condition exists for

solution of k-groups in descending order.

Proof: The proof for ascending order only will be presented. Analogous

arguments hold for the case of descending order.

Sufficient: Suppose that all decision variables offset from U. are

offset from the k-group tear variables by k. When the next k-group is

added, the decisions offset from U. are no longer decision variables.
 1
In order to solve the next to last k-group, values for these variables

must be available. The values are available since these variables have

become tear variables. Thus if a solution procedure holds for n

k-groups it holds for n+l k-groups. It must hold for one k-group,

otherwise it would not be a solution procedure. The condition is

sufficient by induction.

Necessary: Assume that some decision variable offset from U. is not

k greater than a tear variable in the last k-group. When the next

k-group is added, this variable's value must be available to solve the

next to last k-group. It is no longer a decision and is not a tear, but

is an output of a function in the last k-group and hence its value is

not yet calculated. For its value to be known it must be a decision or

tear variable, but this is a contradiction. Thus the solution procedure

does not extend and the necessary condition holds by contradiction. The

theorem is proved.