Branch and Bound
Branch and Bound
Topic 4:
x x !
x x !
x*=(x1*,x2*) └ X *┘+1
2
x x New x*=(x1*,x2*) x x
└x2*┘
Can be removed x
•
x
Can be removed
y y
x1 Feasible se x1
x1* x1* +1
└ ┘ └ ┘
x
x2 X
Creation of Two Subproblems
X
x x !
y
x2* x1
x2* +1
Another interesting observation is that if zIP denotes the optimal objective value of a max-
imizing integer program and zLP is the optimal value of the associated linear program then
zIP ≤ zLP . Moreover, if all the cost coefficients are integers then zIP ≤ bzLP c.
In other words the current optimal value of the associated linear program provides an upper
bound for the actual objective function of integer linear program.
To begin the branch and bound iterative method, we need a feasible solution to the integer
program and call it an incumbent. Here arise an important question as to find this incumbent?
Sometimes it is easy to get the the incumbent. For example,
RLP
x∗
z∗
where RLP stands for relaxed (associated) LP. Note that if the associated LP is infeasible then
the integer LP is also infeasible and we have nothing to do.
Thereafter, systematically consider the values of the variables x∗i , i = 1, . . . , n. See if they all
satisfy the integer conditions imposed on them in the original integer program. If yes, then
stop. We have x∗ an optimal solution of the integer program. Else continue.
We find out those variables xj which are required to be integers but currently in x∗ they do not
take integer values. Among this set of variables, choose any one variable for branching.
RLP
x∗ , z ∗
A j k
A xj ≥ x∗j + 1
j k
xj ≤ x∗j
A
A
A
A
candidate candidate
problem 1 problem 2
The nodes corresponding to the original associated linear program had already been branched.
The nodes corresponding to candidate problems 1 and 2 have not yet been branched and these
are known as terminal nodes at this stage of the algorithm. The list is the collection of all
unfathomed candidate problems corresponding to the terminal nodes at this stage.
Note that we do not branch a node if none of its descendants can give a better solution than that
of incumbent. If zLP (j) denotes the optimal value of the problem at node j and zLP (j) ≤ zI ,
then none of the descendants of node j can improve upon the objective value of the current
incumbent. This is because any descendant candidate problem generated from node j has a
smaller feasible set as that of the problem at node j. So, we shall not branch any further from
node j. Such nodes are called fathomed. Also if at any node the corresponding problem is
infeasible then also such nodes can be chopped off from further branching.
Observation:
(i) b and b creates an enumeration tree, one node at a time and one branch at a time.
(ii) Before branching node j it solves LPP(j) (the associated linear program at node j).
Depending upon the optimal value of LP(j), b and b either fathoms node j or it branches node
j, and create two children nodes having candidate problems.
A b and b method terminates when the list of active nodes is empty; where a node is called
active if it has no children and is not yet fathomed.
(ii) zIP (j) ≤ bzLP (j)c ≤ zI (at current objective incumbent value).
Action: Fathom the node j.
(iii) zLP > zI and optimal solution of LP(j) is feasible for integer program.
Action: Replace incumbent by integral value of LP(j). Since no descendent can be better so
fathom node j.
(iv) bzLP c > zI and the optimal solution of LP(j) is not feasible for integer program.
Action: Branch off node j into two candidate problems and continue with b and b algorithm.
We choose initial incumbent as (0, 0), zI = 0. [Note that we can take some other incumbent to
begin with]
The associated LP is
RLP
LP (1)
k
x = (3.75, 2.25)
z = 41.25
Since bzLP (1)c > zI and x∗ does not satisfy the integer restrictions, so it is case IV.
We can choose any one variable either x1 or x2 (none of them is satisfying integer restriction at
present) for branching. Let us choose x1 . Then
x1 , x2 ≥ 0
and
x2 ≥ 0
Let us look at node 2 (it is an active node). The optimal solution of LP(2) is x∗ = (3, 3) with
zLP (2) = 39.
Since bzLP (2)c > zI = 0 and x∗ satisfies the integer restriction so it is feasible for integer pro-
gram. This is case (iii). So, update the incumbant value zi by 39 and fathomed the node 2.
Next node in the list is node 3. The optimal solution of LP(3) is x∗ = (4, 1.8) and zLP (3) = 41.
Now bzLP (3)c > zI = 39 and x∗ is not integer, so the case (iv). Branch off the node 3 to yield
two candidate problems. The branching is done via the variable x2 as this time as it is not
integer value in the optimal solution of LP(3).
Node 1
LP (1) zI = 0
∗
x = (3.75, 2.25)
z = 41.25
A
A
A
x1 ≤ 3 A x ≥4
A 1
A
A
A
Node 2 Node 3
LP (2) LP (3)
zI = 39
zI = 39 ∗
x = (3, 3) x∗ = (4, 1.8)
z = 39 z = 41.25
fathomed A
A
x2 ≤ 1 A x2 ≥ 2
A
A
A
A
A
Node 4 Node 5
LP (4) LP (5)
zI = 39 ∗
x = (4.44, 2.25) Infeasible
z = 40.55
A fathomed(case(ii))
A
x1 ≤ 4 A x1 ≥ 5
A
A
A
A
Node 7
Node 6
LP (7) zI = 40
fathomed (case(i)) LP (6) ∗
x = (5, 0) fathomed (case(iii))
∗
x = (4, 1)
z = 40
z = 37
x2 X
9
x2*isX not integer
|
x x
|
└ x2x*┘+1
1
|
6
|
x2*
|
2
└ ┘
|
Can be removed
x
|
• X*=(3.75, 7/2)
|
y
|
Feasible se
| | | | |
5
|
6
x1Feasible se
x
x2 X2
X
– X
x x –!
–
x x –
(3,3)
•
x
–
• (4,1.8) – x =2
2
• (4,1.8)
y – •
(4.4,1)
X2 ≤1
x2* x1 x2* I I I I I x1
Feasible set of
└ ┘ Feasible set of
LP(2)
Feasible set of
LP(3) └ ┘ x2* +1 Infeasible LP(5)
LP(4)
└ ┘
The algorithm can be appropriately modified to deal minimization integer program; or one can
take (−z) instead of z in the objective function and proceeds like a maximization problem.
For a branch and bound method to work well, the bounding strategy must provide an upper
bound fairly close to the maximum objective value with little computational effort. There are
various search strategies that have been proposed in the literature what we have demonstrated
above was based on least upper bound criterion.
The efficiency of b and b method obviously depends upon how good is branching strategy and the
search strategy. The search strategy which allows for extensive pruning and early updatation
of the incumbent is considered extremely good as this leads to less number of branch/nodes to
search and thereby making the iterative scheme to terminate with little computational efforts.