lower bounding cost of this branch is less, then we continue the search of this branch,

proceeding as we did in the first branch, with one exception. We now have an upper

bounding cost and if at any point we find a design, either fully discrete of not, higher

in cost than our upper bounding design, we fathom this node and implicitly fathom

any branches of this design. However, as long as improvement appears possible, the

branch is searched until a discrete design acceptably close to the lower bounding

cost is found or all alternatives are exhausted. If a discrete design with a lower cost

than the lowest cost discrete design of the previous branch is found, it becomes the

new upper bound on cost. If this cost is sufficiently close to the continuous lower

bounding cost, then the search is concluded. Otherwise, another variable is chosen

to branch on. When exploring alternatives within any main branch, the same basic

branch-and-bound approach is applied within the "sub-branch." Below we will

show how the branch-and-bound method is applied to our problem.

Before we can apply the branch-and-bound method as described above, we must

first have a feasible solution point from which to start. To find such a solution, we

use one of the methods described earlier in the section entitled *Constraint Resolution*

calculate the *continuous *pipe size necessary to reduce the pressure loss to the next

level as described there. This is done by combining eq 4-2 and 4-4 to obtain

(-1/(5+*b*+*c*))

∆*P*hp,i - ∑ (∆*P*s + ∆*P*r ) + ∆*P*cv + ∆*P*he

i

j

j ≠ *j*1

(5-13)

=

2+*c*

2+*c*

(*a *ε (4/π)

˙

.

In this case the pipe segment index *j*1 is the pipe segment whose diameter we have

chosen to increase and the consumer index *i *is for the consumer with the second

highest pressure loss at the heating plant as determined by eq 4-2. We continue to

use method A, which essentially repeats steps 1 and 2 until all the constraints that

were previously violated are now satisfied. When we have finished, we can check

our application of the method by taking the pipe segments that were in the sets of

those constraints previously violated and decreasing them to the next lowest pipe

diameter one at a time. If our application of method A was correct, each pipe

diameter that is decreased should result in the violation of at least one constraint.

At the conclusion of the use of method A, we will have a number of pipe segments

whose diameters are continuous as a result of the refinement process used by the

method. To obtain discrete diameter values for these pipe segments, we use the

branch-and-bound method as described above. Note that the *unconstrained discrete*

solution, what we have called our "optimal independent design," will form a greater

lower bound than the *unconstrained continuous *solution. It may not, however, form

a greater lower bound than the *constrained continuous *solution, which we have

chosen not to attempt to find owing to the computational effort involved, as

discussed earlier. What we have found using method A is a feasible solution whose

cost is greater than the *unconstrained discrete *solution. The solution we have must

also be higher in cost than the *constrained continuous *solution, since the deletion of

the requirement of discrete sizes for those pipe segments that already have discrete

sizes would allow us to find a feasible solution at some lower cost. We can not be

certain, however, that the solution of method A is lower in cost than the *constrained*

59

Integrated Publishing, Inc. |