larger diameters would be better. Thus, it is unclear from this analysis whether we

should try to choose smaller or larger pipes for increased diameters to satisfy

constraints. We do know that incremental increases in the discrete sizes of pipes will

be smaller in general for the smaller pipes. However, this does not necessarily mean

that we will be able to get closer to just satisfying the constraint in all cases by

increasing the diameter of the smaller pipes. Fortunately, the branch-and-bound

method mentioned earlier will provide us with a general solution strategy despite

our inability to better characterize the nature of the path to the solution.

The objective of the branch-and-bound method is to use what is known about

designs already explored to reduce the number of remaining ones that must be

examined in detail. An additional caveat is that we would like to do so without

dismissing any designs superior to the best feasible ones identified. According to

Reklaitis et al. (1983), the branch-and-bound algorithm is the most widely used

method for mixed integer problems and is the basis for most commercial computer

codes for solving such problems. The essence of the branch-and-bound method is

that it breaks the problem down into branches, each of which corresponds to some

particular choice of a single discrete decision variable.

The first step in the method is to compute the optimal solution to the problem with

all the variables assumed to be continuous. This becomes our global lower bound.

The branching usually starts by choosing what is felt to be the most fruitful branch

(variable) to explore; some criteria are given in Reklaitis et al. (1983). A discrete value

for the variable of this branch is chosen; this will be one of the discrete values

bracketing the optimum continuous value. The lower bounding cost for this branch

is found by finding the optimum continuous values of the remaining decision

variables with the branching variable fixed at its discrete value. At this point we can

explore the discrete designs within this branch by branching on the other variables

or we can go directly to the next branch. If we continue to explore this branch and

we find a discrete design sufficiently close to our lower bounding continuous

design, we can stop searching and accept this design. Otherwise, we move on to the

next branch. If we decide to search this branch further, we do so by comparing costs

obtained for designs within the branch by making permutations of the other

decision variables in turn to their bracketing discrete values.

This process continues until a feasible design with discrete values for all those

variables requiring such values is found. This is our first candidate design and its

cost becomes our upper bounding cost. Through the remainder of the process all

solutions will be compared in cost to this one until another feasible discrete design

with a lower cost is found. Any designs with higher cost will immediately be

rejected, and if continuous variables are still included in these designs for variables

that must ultimately take on discrete values, then all other designs within that

branch will be rejected as well. This can be done since we know that restricting any

of the continuous variables to discrete values will only increase the cost. The process

of rejecting these other designs for which the cost is never computed is called

"implicit fathoming," as opposed to "explicit fathoming" where the cost is com-

puted and the design is rejected because its cost exceeds our upper bounding cost.

Any remaining feasible discrete designs are also compared to the lower bounding

cost for the branch found with continuous values of the non-branching variables. If

any are sufficiently close to this lower bound, the search of the branch is concluded

and the design found is accepted as an adequate design representative of what can

be expected within the branch.

The next branch to be explored will use the other bracketing value of the first

branching variable. Its lower bounding continuous cost design is compared to our

current upper bounding cost from the best design of the previous branch. If the

58

Integrated Publishing, Inc. |