Optimization

Techniques
for AI
Lecture
CS/AI 13
2101
Branch & Bound Algorithm-
(0, 1) Knapsack Problem
(0, 1)-Knapsack Problem

Maximize z = 8x1 + 11x2 +

P(0,1) 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xi ∈ { 0, 1} for all i = 1, 2,
3, 4
Relaxation
Maximize z = 8x1 + 11x2 +
P(0,1) 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xi Relaxation
∈ { 0, 1} for all i = 1, 2, (0,1) constraints
is relaxed, so the
3, A4 primary variables can
assumption is that take any value
the relaxed between 0 and 1.
problem is easier
Maximize
to solve z = 8x1 + 11x2 +
PLP 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
0 ≤ xi ≤1 for all i = 1, 2, 3,
4
 Simple Technique to Solve
Psimple
A LP technique to solve LP-relaxed Knapsack
Problem PLP
Technique to solve
1. Arrange the variables in the decreasing order of
the ratio as follows.
2. Choose the largest k such that
3. Assign , for i =1, 2, .., k
 P(0, 1)
Maximize z = 8x1 + 11x2 + 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14 P1(0, 1)
xi ∈ { 0, 1} for all i = 1, 2, 3, 4
Max z = 6+8x1 +
Relaxation 11x2 + 4x4
PLP 5x1 + 7x2 + 3x4 ≤ 10
Maximize z = 8x1 + 11x2 + 6x3 + 4x4
xi ∈ { 0, 1} for all i
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xi ∈ [ 0, 1] for all i = 1, 2, 3, 4
= 1, 2, 4 P2(0, 1)

Solve Max z = 8x1 + 11x2

+ 4x4
5x1 + 7x2 + 3x4 ≤
14
The solution is not integer. xi ∈ { 0, 1} for all i
x3 is 0.5 and is branching = 1, 2, 4
variable to generate two
subproblems. One with x3 = 1,
and the other x3 =0
 P11(0,
Max z = 6+8x1 +
1)
P2(0, 1) 11x2 + 4x4
x3 =
5x1 + 7x2 + 3x4 ≤ 10
0 x2 =1
P(0, 1)
xi ∈ { 0, 1} for all i
Max
= 1, z4 = 17+8x1 +
4x4
x2 =
x3 = P1(0, 1) 0 5x1 + 3x4 ≤ 3
1
xi ∈ { 0, 1} for all i
Solve- k=0, x1 =0.6 , x4
x2 =
1
=
=0
1, 4
 P2(0, 1)

x3 =
0

P(0, 1)

x2 =
x3 = P1(0, 1) 0
1

x2 =
1 P11(0, 1)
Solve- k=0, x1 =0.6 ,
x4 =0
 P2(0, 1)

x3 =
0

P(0, 1)

x2 =
x3 = P1(0, 1) 0
1

x2 =
1 P11(0, 1)
Solve- k=0, x1 =0.6 ,
x4 =0

P12(0,
1)
Max z = 6+8x1 +
11x2 + 4x4 Max z = 6+8x1 + 4x4 Solve- k=2, x1 =1 , x4
5x1 + 3x4 ≤ 10 =1
5x1 + 7x2 + 3x4 ≤ 10
x2 =0 xi ∈ { 0, 1} for all i
xi ∈ { 0, 1} for all i = 1, 4
 P2(0, 1)

x3 =
0

P(0, 1)

P12(0, 1)
P1(0, 1) x2 = P112(0, 1)
x3 = 0
1

x2 = x1 =
1 P 11
(0, 1)
0

x1 = P111(0, 1)
1
P(0, 1) INFEASIBLE
Maximize z = 8x1 + 11x2 + 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xi ∈ { 0, 1} for all i = 1, 2, 3, 4
 P2(0, 1)

x3 =
0

P(0, 1)

P12(0, 1)
P1(0, 1) x2 = P112(0, 1)
x3 = 0
1

x2 = x1 =
1 P 11
(0, 1)
0

x1 = P111(0, 1)
1
P(0, 1) INFEASIBLE
Maximize z = 8x1 + 11x2 + 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xi ∈ { 0, 1} for all i = 1, 2, 3, 4
Branch-and-bound strategy
 It is a tree search.
 It gradually (as it traverses the tree) assigns
values to variables
 Root node – no variable is assigned

 Leaf node- all variables are assigned

 Intermediate node- some variables are assigned

values and some are not.

 A mechanism to generate branches when
searching the solution space
 A mechanism to generate a bound so that many
branches can be terminated

12
Tree
Search

x1 ←0 1→

x2 ←0 1→

x3 ←0 1→

x=
(1,0,0)T
Branch-and-bound strategy
 It is efficient in the average case
because many branches can be
terminated very early.

 Although it is usually very efficient, a

very large tree may be generated in the
worst case.

 Many NP-hard problem can be solved by

B&B efficiently in the average case;
however, the worst case time complexity
is still exponential. 14
How to find the upper
bound?
How to find the lower bound?
How to determine branching
variables?
How to expand the tree?
 By Depth-First- Search
 By the Best-First Search

When no to expand a node?

15
Branch & Bound Method
Slide 1- Initialization
 Maintain a structure L as the list of problems
(nodes) to solve ( set of Knapsack Subproblems).
We shall take L to be a Stack OR Priority Queue
 The algorithm runs till L is not empty
 A lower Bound LB - value of the z at the best
known integer solution. It is global variable. One
value for the entire tree, gets updated time to time.
 incumbent as the best integer solution found so
far. It goes with LB.
 A upper bound at every node. It is local
 Any node is labeled (not visited/visited/fathomed/qualified for
expansion )
 Initially L has only the original problem
 Initially lower Bound LB = −∞,
Branch & Bound Method
Select a Candidate Problem
CANDIDATE PROBLEM-
If L is empty, STOP
If L is not empty.
Take a Candidate problem from list L (a (0, 1)
knapsack problem)
RELAXATION - The LP relaxation of Candidate is .
FEASIBILITY CHECK - Check if infeasible.
If infeasible Select another problem from L.
Else, solve
Branch & Bound Method
Slide 3- When is solved
UPDATING BOUND-
if the optimal solution is integer,
if > LB then update LB as , and incumbent as
else, no change in LB, incumbant
Node k is not to be expanded. Select another problem from
L
if the optimal solution is not integer
if ≤ LB, node k is Fathomed. Select another problem from
L

BRANCH AND GENERATE SUBPROBLEMS

if the optimal solution is not integer
if > LB then Choose xj which is fractional as branching
variable
Create two new problems and and put them on L
To Expand a node
Select a node from L to be expanded, say
P(0,1).
Determine Branching variable say How to select?
x_branch
LIFO- if L is a stack
Generate two subprblems.
P1(0,1) -P(0,1) with additional constraint …. - if L is some other
x_branch =1 structure
P2(0,1) -P(0,1) with additional constraint
x_branch =0
Solve two relaxed subprblems.
Select a node from L to be expanded
P1LP and P2LP
Only if ittoqualifies
Add them L to be expanded
1. The relaxed problem PLP is feasible
2. The solution of PLP is not integer
3. Its upper bound of PLP is not
smaller than the global LB
 if the optimal solution is not
integer
if ≤ LB, node k is Fathomed.
SelectPanother
2
(0, 1)
problem from L

x3 = if the optimal solution

0 is integer, if > LB
then update LB as ,
P(0, 1)
and incumbent as
P12(0, 1)
P1(0, 1) x2 = P112(0, 1)
x3 = 0
1

x2 = x1 =
1 P 11
(0, 1)
0

x1 = P111(0, 1)
1
P(0, 1) INFEASIBLE
Maximize z = 8x1 + 11x2 + 6x3 + 4x4
5x1 + 7x2 + 4x3 + 3x4 ≤ 14 If infeasible
xi ∈ { 0, 1} for all i = 1, 2, 3, 4 Select another
problem from L.
Else,
solve
Maximize 24 x1 + 17 x2 + 12 x3 + 6 x4
such that 10 x1 + 8 x2 + 6 x3 + 5 x4 ≤
15
x1,x2,x3,x4 {0,1}
LB = −∞ LP solution