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.
Branch-and-bound method
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
Previous Page
