[go: up one dir, main page]

0% found this document useful (0 votes)
15 views8 pages

Branch and Bound

Uploaded by

Sathiya Priya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
15 views8 pages

Branch and Bound

Uploaded by

Sathiya Priya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Module 8 1

Topic 4:

Branch and Bound Algorithm:


Extensive numerical experiments in solving integer programming problems arising in practice
indicate that cutting plane methods require large number of steps before termination while
there is another method namely branch and bound method which gives much better results for
solving integer linear programs. This lecture shall focus on branch and bound (b and b) method.
Before formally describing the method, let us first understand geometrical how we can retrieve
the optimal solution. Suppose there is some integer program whose associated LPP has an
optimal solution x∗ . Let the j th variable value x∗j does not satisfy the integer condition. Then
j k j k
x∗j has fractional point. So, if we consider a strip x∗j ≤ xj ≤ xkj + 1 in the feasible set of
the associated LPP, it contains no point having xj value integer. In other words this strip can
Feasible se Feasible se
not have optimal solution of the integer LPP with xj as integer. Thus, removing this strip from
the feasible set will not affect the overall optimal solution of the integer LPP. This is precisely
what is done in b and b method. x x
x2 X
x2 X
x2*is not integer X X

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 !

One part of feasible x x


region •
x
Second part of
feasible region

y
x2* x1
x2* +1

c Copyright Reserved IIT Delhi


2

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,

max 16x1 + 22x2 + 12x3


subject to 15x1 + 7x2 + 4x3 ≤ 14
xi ∈ {0, 1}, i = 1, 2, 3

The starting incumbent could be x1 = 1, x2 = 1, x3 = 0.


But this need not be the case always. Most b and b methods have a special subroutine run at
the beginning of the methods that tries to get a good feasible solution. For the time being we
assume that we have an incumbent in hand with objective function zI .
The three basic ingredients in any b and b technique are:
(i) a bounding strategy
(ii) a branching strategy
(iii) a search strategy

We now explain how a b and b method works.


First solve the associated linear program and represent its optimal solution and optimal value
by a node, like

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.

c Copyright Reserved IIT Delhi


3
j k j k
The branching is done by incorporating additional constraints xj ≤ x∗j and xj ≥ x∗j + 1,
where xj is the selected branching variable. These constraints lead to two subproblems which
are linear programs only. These problems are also called candidate subproblems.
This can be depicted in graph like:

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.

c Copyright Reserved IIT Delhi


4

For maximization integer program, we have four cases:


(i) LP(j) is infeasible.
Action: Fathom the node j.

(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 present an example to illustrate the b and b method.


Example:8.4.1 Consider the pure integer program.

max 8x1 + 5x2


subject to x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1 , x2 ≥ 0
x1 , x2 are integers.

We choose initial incumbent as (0, 0), zI = 0. [Note that we can take some other incumbent to
begin with]
The associated LP is

LP(1): max 8x1 + 5x2


subject to x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1 , x2 ≥ 0

Optimal solution of LP(1) is x∗ = (3.75, 2.25) with zLP (1) = 41.25.

RLP
LP (1)
k
x = (3.75, 2.25)
z = 41.25

c Copyright Reserved IIT Delhi


5

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

LP(2): max 8x1 + 5x2


subject to x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1 ≤ xk1 = 3
 

x1 , x2 ≥ 0

and

LP(3): max 8x1 + 5x2


subject to x1 + x2 ≤ 6
9x1 + 5x2 ≤ 45
x1 ≥ xk1 + 1 = 4
 

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).

c Copyright Reserved IIT Delhi


6

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

c Copyright Reserved IIT Delhi


7
Feasible se
The optimal solution of the given integer program is x∗1 = 5, x∗2 = 0 with the optimal ob-
jective value 40.
The above tree can be graphically illustrated as follows:x

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.

c Copyright Reserved IIT Delhi


8

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.

c Copyright Reserved IIT Delhi

You might also like