A as our lower bounding cost, we can not be certain that this is the greatest lower

bound. If the application of the branch-and-bound method finds feasible solutions

with costs lower than our solution found by method A, then we must from that point

on use the *unconstrained discrete *solution as the greatest lower bound.

Note that, similar to method A (Fig. 9), method B (Fig. 10) would also provide a

number of pipe segments whose diameters are continuous as a result of the

refinement process used. Thus, we would proceed in the same manner with the

branch-and-bound method regardless of which of the two methods had been used

for the pipe size refinement process.

The application of the branch-and-bound method to our feasible solution of

method A or B is straightforward and proceeds as described earlier. Many of the

branches will have infeasible designs, since we know decreasing any of the continu-

ous pipe diameters will result in the violation of at least one constraint, unless other

pipe diameters have also been increased. Thus, any branch that only decreases pipe

diameters in any one of the combinations in which they appear in the previously

violated constraints will be infeasible and need not be explored.

Consider a hypothetical case where we have four pipe segments with continuous

diameters after the application of either method A or B. If we limit ourselves to only

the two discrete pipe sizes that bracket the continuous values found, we will have

24 = 16 possible discrete solutions. A "tree" diagram of the problem is shown in

Figure 13. The symbols within each "node" of the tree represent the particular case

being evaluated. The "0" symbol indicates the continuous pipe size as found by

either method A or B. A "+" symbol indicates the next larger discrete pipe size and

a "" symbol indicates the next smaller discrete pipe size. The sequence of the

symbols represents the order of the four pipe segments under investigation. As

noted above, any possibilities that only decrease the size of one or more pipe

segments are immediately known to be infeasible. These nodes have been shown

with dotted outlines in Figure 13.

Applying the branch-and-bound method, we would proceed initially by choos-

ing the first pipe segment to branch on. Starting at the top of Figure 13, we branch

on the first pipe segment by computing the value of the objective function with the

branching diameter, rounded both up and down to the adjacent discrete diameter

values. However, we notice that one of the options, the ( 000) case, is infeasible.

Thus, there is no use in computing the value of the objective at that point since it's

of no use as a lower bound on the constrained problem. In this case we then proceed

further down this branch in search of a feasible case. Suppose that we find that the

( + + 0) is the first feasible case in this branch. We then branch on the last pipe

segment by examining the cases ( + + +) and ( + + ). Assume that we find both of

these to be feasible, but the ( + + ) case is lower in cost. This is our first completely

discrete and feasible design. It now becomes our upper bounding cost. If this cost is

sufficiently close to our current lower bounding cost of the (0000) case, then we can

(0000)

(+000)

(-000)

(+-00)

(-+00)

(++00)

(--00)

(--+0)

(---0)

(+++0)

(++-0)

(+-+0)

(+--0)

(-++0)

(-+-0)

(++++) (++++) (++-+)

(++--)

(-+++)

(-++-)

(-+--)

(--++)

(--+-)

(---+)

(----)

(+-++)

(+-+-)

(+--+)

(+---)

(-+-+)

60

Integrated Publishing, Inc. |