Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | Branch-and-Bound (B&B) Algorithm

The first B&B algorithm was developed in 1960 by A. Land and G. Doig for the general mixed and pure ILP problem.

**Branch-and-Bound (B&B) Algorithm**

The first
B&B algorithm was developed in 1960 by A. Land and G. Doig for the general
mixed and pure ILP problem. Later, in 1965, E. Balas developed the additive
algorithm for solving ILP problems with pure binary (zero or one) variable. The
additive algorithm's computations were so simple (mainly addition and
subtraction) that it was hailed as a possible breakthrough in the solution of
general ILP. Unfortunately, it failed to produce the desired computational
advantages. Moreover, the algorithm, which initially appeared unrelated to the
B&B technique, was shown to be but a special case of the general Land and
Doig algorithm.

This
section will present the general Land-Doig B&B algorithm only. A numeric
example is used to explain the details.

**Example
9.2-1**

The
lattice points (dots) in Figure 9.6 define the ILP solution space. The
associated continuous LPI problem at node 1 (shaded area) is defined from ILP
by removing the integer restrictions. The optimum solution of LPI is x_{1}
= 3.75, *x _{2}* = 1.25,
and

Because
the optimum LPI solution does not satisfy the integer requirements, the B&B
algorithm modifies the solution space in a manner that eventually identifies
the ILP optimum. First, we select one of the integer variables whose optimum
value at LPI is not integer. Selecting x_{l} (= 3.75) arbitrarily, the
region 3 < x_{l}
< 4 of the LPI solution space
contains no integer values of *x _{1,}* and thus can be eliminated as
nonpromising. This is equivalent to replacing the original LPI with two new
LPs:

Figure
9.7 depicts the LP2 and LP3 spaces. The two spaces combined contain the same
feasible integer points as the original ILP, which means that, from the
standpoint of the integer solution, dealing with LP2 and LP3 is the same as
dealing with the original LPl; no information is lost.

If we *intelligently* continue to remove the regions
that do not include integer solutions (e.g.,
3 < x_{l} < 4 at LPl) by imposing the
appropriate constraints, we will eventually produce LPs whose optimum extreme
points satisfy the integer restrictions. In effect, we will be solving the ILP
by dealing with a sequence of (continuous) LPs.

The new
restrictions, x_{1} ≤ 3 and *x _{1}* ≥ 4, are
mutually exclusive, so that LP2 and LP3 at nodes 2 and 3 must be dealt with as
separate LPs, as Figure 9.8 shows. This dichotomization gives rise to the
concept of branching in the B&B algorithm. In this case, x

The
optimum ILP lies in *either* LP2 *or* LP3. Hence, both subproblems must be
examined. We arbitrarily examine LP2 (associated with x_{1} ≤3) first:

The LP2
solution satisfies the integer requirements for x_{l} and *x _{2}.* Hence, LP2 is said to be
fathomed, meaning that it need not be investigated any further because it
cannot yield any

We cannot
at this point say that the integer solution obtained from LP2 is optimum for
the original problem, because LP3 may yield a better integer solution with a
higher value of *z.* All we can say is that *z* = 23 is a
lower **bound** on the optimum (maximum)
objective value of the original ILP. This means that any unexamined subproblem
that cannot yield a better objective value than the lower bound must be
discarded as nonpromising. If an
unexamined subproblem produces a better integer solution, then the lower bound
must be updated accordingly.

Given the
lower bound *z* = 23, we examine LP3
(the only remaining unexamined subproblem at this point). Because optimum *z* = 23.75 at LPI *and all the coefficients of the objective* *function happen to be integers, *it is impossible that LP3 (which is
more restrictive than LPl) will* *produce
a better integer solution with *z* > 23. As a result, we discard LP3
and conclude that it has been *fathomed.*

The
B&B algorithm is now complete because both LP2 and LP3 have been examined
and fathomed (the first for producing an integer solution and the second for
failing to produce a *better *integer
solution). We thus conclude that the optimum ILP solution is the one associated* *with the lower bound-namely, x_{1}
= 3, *x _{2},* and

Two
questions remain unanswered regarding the procedure.

a)
At LPI, could we have selected *x _{2}* as the

b)
When selecting the next subproblem to be examined,
could we have solved LP3 first in-stead of LP2?

The
answer to both questions is "yes," but ensuing computations could
differ dramatically. Figure 9.9 demonstrates this point. Suppose that we
examine LP3 first (instead of LP2 as we did in Figure 9.8). The solution is x_{I}
= 4, x_{2} = .83, and *z* = 23.33 (verify!). Because *x _{2}* (= .83)
is noninteger, LP3 is examined further by creating
subproblems LP4 and LPS using the branches

We now
have three "dangling" subproblems to be examined: LP2, LP4, and LP5.
Suppose that we arbitrarily examine LP5 first. LP5 has no solution, and hence
it is fathomed. Next, let us examine LP4. The optimum solution is x_{l}
= 4.5, x_{2} = 0, and *z* =
22.5. The noninteger value of *x _{1} *leads to the two branches

Now,
subproblems LP2, LP6, and LP7 remain unexamined. Selecting LP7 for examination,
the problem has no feasible solution, and thus is fathomed. Next, we select
LP6. The problem yields the first integer solution (x_{l} = 4, *x _{2}* = 0,

(= 20) on the optimum ILP objective
value. We are now left with subproblem LP2, which yields a better integer solution *(x _{1}* = 3,

The
solution sequence in Figure 9.9 (LPl --> LP3 --> LP5 --> LP4 -->
LP7 --> LP6 --> LP2) is a worst-case scenario that, nevertheless, may well
occur in practice. In Figure 9.8, we were lucky to "stumble" upon a
good lower bound at the very first subproblem we examined (LP2), thus allowing
us to fathom LP3 without investigating it. In essence, we compieted the
procedure by solving a total of two LPs. In Figure 9.9, the story is different: We needed to solve
seven LPs before the B&B algo-rithm could be terminated.

**Remarks.** The example points to a
principal weakness in the
B&B algorithm: Given multiple choices, how do we select the next subproblem
and its branching variable? Although there are heuristics for enhancing the
ability of B&B to "foresee" which branch can lead to an improved
ILP solution (see Taha, 1975, pp. 154-171), solid theory with consistent
results does not exist, and herein lies the difficulty that plagues
computations in ILP. Indeed, Problem 7, Set 9.2a, demonstrates the bizarre
behavior of the B&B algorithm in investigating over 25,000 LPs before
optimality is verified, even though the problem is quite small (16 binary
variables and 1 constraint). Unfortunately, to date, and after more than four
decades of research coupled with tremendous advances in computing power,
available ILP codes (commercial and academic alike) are not to-tally reliable,
in the sense that they may not find the optimum ILP solution regardless of how
long they execute on the computer. What is even more frustrating is that this
behavior can apply just the same to some relatively small problems.

**AMPL
Moment**

AMPL can
be used interactively to generate the B&B search tree. The following table
shows the sequence of commands needed to generate the tree of Example 9.2-1
(Figure 9.9) starting with the continuous LPO. AMPL model (file
ampIEx9.2-1.txt) has two variables x_{l} and x_{2} and two
constraints c_{0} and c_{l}. You will find it helpful to synchronize
the AMPL commands with the branches in Figure 9.9.

**Solver
Moment**

Solver
can be used to obtain the solution of the different subproblems by using the
add/change/delete options in the **Solver
Parameters** dialogue box.

**Summary of the B&B Algorithm.** We now
summarize the B&B algorithm. Assuming a maximization problem, set an
initial lower bound *z* = - ¥ on the
optimum objective value of ILP. Set *i* = 0.

**Step 1.** *(Fathoming/bounding).* Select LPi, the next subproblem to be
examined. Solve LPi, and attempt to fathom it using one of three conditions:

a)
The optimal z-value of *LPi* cannot yield a better objective value than the current lower
bound.

b)
LPi yields a better feasible integer solution than
the current lower bound.

c)
*LPi *has no
feasible solution.

Two cases
will arise.

a)
If LPi is
fathomed and a better solution is found, update the lower bound. If all subproblems have been
fathomed, stop; the optimum ILP is associated with the current finite lower
bound. If no finite lower bound exists,
the problem has no feasible solution. Else, set *i* = *i* + 1, and repeat step 1.

b)
If LPi is
not fathomed, go to step 2 for branching.

**Step 2. ***(Branching).* Select
one of the integer variables *x _{j},* whose optimum value

(where *[v]* defines
the largest integer *≤ v)* by creating two LP subproblems
that correspond to

The given
steps apply to maximization problems. For minimization, we replace the lower
bound with an upper bound (whose initial value is *z* = +¥).

The
B&B algorithm can be extended directly to mixed problems (in which only
some of the variables are integer). If a
variable is continuous, we simply never select it as a branching variable. A
feasible subproblem provides a new bound on the objective value if the values
of the discrete variables are integer and the objective value is improved
relative to the current bound.

**PROBLEM SET **9.2A^{}

1. Solve the ILP of Example 9.2-1 by the B&B algorithm starting with *X _{2}* as the branching variable. Start
the procedure by solving the subproblem associated with

2. Develop the B&B tree for each of the following problems. For
convenience, always select X_{l} as the branching variable at node 0.

*7. TO RA/Solver */* AMPL Experiment. *The
following problem is designed to demonstrate the* *bizarre behavior of the B&B algorithm even for small problems.
In particular, note how many subproblems are examined before the optimum is
found and how many are needed to verify optimality.

a) Use TORA's automated option to show that although the optimum is found
after only 9 subproblems, over 25,000 subproblems are examined before
optimality is confirmed.

b) Show that Solver exhibits an experience similar to TORA's. *[Note:* In Solver, you can watch the
change in the number of generated branches (subproblems) at the bottom of the
spreadsheet.]

c) Solve the problem with AMPL and show that the solution is obtained
instantly with oMIP simplex
iterations and 0 B&B nodes. The reason for this superior perfor-mance can
only be attributed to preparatory steps performed by AMPL and/or the CPLEX
solver prior to solving the problem.

*8. TORA Experiment. *Consider the following ILP:

Use TORA's B&B user-guided option to generate the search tree with
and without acti-vating the objective-value bound. What is the impact of
activating the objective-value bound on the number of generated subproblems?
For consistency, always select the branching variable as the one with the
lowest index and investigate all the subproblems in a current row from left to
right before moving to the next row.

**9. TORA Experiment. *Reconsider Problem 8 above. Convert the problem into an equivalent 0-1
ILP, then solve it with TORA's automated option. Compare the size of the search
trees in the two problems.

*10. AMPL Experiment. *In the following 0-1 ILP use interactive AMPL to generate the
asso-ciated search tree. In each case, show how the z-bound is used to fathom
subproblems.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.