accept this solution and terminate the search. Let's assume, however, that this is not

the case.

Thus, we now need to start the process of "backtracking" and examining the

delayed cases that we passed over. We begin by examining the case ( + 0). Since

we found that the ( + 00) case was infeasible, then we immediately know that the

( + 0) case must be infeasible as well, since it only decreases diameters from an

infeasible case. Consequently, the ( + ) case must be infeasible as well for the same

reason. The ( + +) case might be feasible and let's assume that we find this to be

true. Assume that the cost of this completely discrete design is less than the cost of

the ( + + ) design and thus it becomes our new upper bound on cost. Again, we

would compare the cost of this upper bound with the lower bounding cost of the

(0000) design and decide if further searching is warranted. Let's assume that we are

still not satisfied with the gap between the upper and lower bounding costs, so we

decide to continue our search.

Backtracking further, we explore the alternatives ( 0 +), ( + +), ( + ) and

( +). Assume that we find these to all be infeasible. We then return back to the

other side of the first branch explored, the alternatives in the (+ 000) branch. Assume

that we find that both the (+ + 00) and the (+ 00) cases are feasible, but the (+ 00)

case has a lower cost. Thus, we defer any further exploration of the (+ + 00) branch.

We continue in the (+ 00) branch by exploring the (+ + 0) case and the (+ 0) case.

Suppose that both cases are feasible, but the (+ 0) case has a lower cost. Thus, we

continue by checking the cost and feasibility of the (+ +) and the (+ ) cases.

Assume that the (+ ) case is infeasible, but the (+ +) case is not only feasible

but lower in cost than our former upper bounding cost of the ( + +) design. Assume

that this cost is indistinguishable from the lower bounding cost of the (0000) case,

and thus we accept the (+ +) design and terminate the search.

As illustrated here, one of the techniques used by the branch-and-bound method

is to continuously move the upper and lower bounding costs closer together until

the remaining possible improvement (i.e., reduction in cost) does not justify further

effort. At this point, the search can be stopped regardless of how many alternatives

have actually been explored. This process is accomplished by moving the upper

bound down as low as possible, i.e., finding the "least upper bound." The least upper

bounding cost is always the lowest cost feasible discrete design found up to that

point in the process. The difference between the lower and upper bounding costs is

also refined by finding the "greatest lower bound." The lower bounding cost is

initially determined by the continuous feasible design found by either method A or

B. As we proceed with the branching process, we will find lower bounding costs

within that branch for designs that have some, but not all, of their diameters at

discrete values. These greater lower bounding costs allow us to refine the difference

between the upper and lower bounding costs for that branch only. They also,

however, may tell us that further exploration of the branch is unwarranted if they

exceed our current upper bounding cost.

Once we have reached a solution by the method described above, there is an

additional area where we can seek further cost reductions. Note first that those

consumers who did not have their constraint of eq 4-2 violated will have pressure

losses in their control valves greater than the minimum allowed values. We then

observe that if these excessive pressure losses were absorbed by decreasing the sizes

of the pipes servicing only these consumers, our constraints would still be satisfied,

but the cost of the piping network would be reduced by use of the smaller pipe sizes.

This possibility is explored in the next chapter.

The procedure we have developed in this chapter to solve for the pipe diameters

in a general multiple-pipemultiple-consumer system may be used with any

number of pipes and consumers. In the next chapter we will illustrate the use of the

method presented here on a simple example.

61

Integrated Publishing, Inc. |