accept this solution and terminate the search. Let's assume, however, that this is not
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.