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.
Solution by the branch-and-bound method
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
by Pipe Size Refinement. For example, if we use the method A step 2 (Fig. 9), we
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))
∆Php,i - ∑ (∆Ps + ∆Pr ) + ∆Pcv + ∆Phe
i
j
j ≠ j1
(5-13)
=
dj1
2+c
b
2+c
(a ε (4/π)
˙
A6 md L )j1
.
In this case the pipe segment index j1 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
discrete solution that we seek. For this reason, when we use the cost found in method
59
Previous Page
