# MB0048 : What are the meaning and role of the lower bound and upper bound in the branch and bound method?

Posted October 3, 2011

on:**MB0048 : What are the meaning and role of the lower bound and upper bound in the branch and bound method?**

**Answer: – **Sometimes a few or all the variables of an IPP are constrained by their upper or lower bounds or by both. The most general technique for a solution of such constrained optimization problems is the branch and bound technique. The technique is applicable to both all (or pure) IPP as well as mixed IPP. The technique for a maximization problem is discussed below:

Let the IPP be

Maximize–––––––––––––––––––––––––––– (1)

Subject to the constraints

––––––––––––––––––– (2)

*x _{j}* is integer valued ,

*j = 1, 2, …….., r (< n)*–––––––––––––––––- (3)

*x _{j }*> 0 ………………….

*j = r + 1, …….., n*––––––-––––––––––––––– (4)

Further let us suppose that for each integer valued x_{j}, we can assign lower and upper bounds for the optimum values of the variable by

*L _{j} ≤ x_{j} ≤ U_{j} j = 1, 2, …. r* –––––––––––––––––––––––––– (5)

This is the main idea behind “the branch and bound technique”.

Consider any variable *x _{j},* and let

*I*be some integer value satisfying

*L*. Then clearly an optimum solution (1) through (5) also satisfies either linear constraint.

_{j}£ I £ U_{j}– 1*x _{j} ³ I + 1* –––––––––––––––––––––––––––––– (6)

Or the linear constraint x_{j} ≤ I –––––––––––––––––––––––––––––– (7)

To explain how this partitioning helps, let’s assume that there were no integer restrictions (3), and it yields an optimal solution to LPP – (1), (2), (4) and (5). This indicates *x _{1} *= 1.66 (for example).

Then we formulate and solve two LPPs each containing (1), (2) and (4). But (5) for* j = 1* is modified to be *2 ≤ x _{1} ≤ U_{1}* in one problem and

*L*in the other. Further to each of these problems, process an optimal solution satisfying integer constraint (3).

_{1}≤ x_{1}≤ 1Then the solution having the larger value for z is clearly the optimum for the given IPP. However, it usually happens that one (or both) of these problems have no optimal solution satisfying (3), and thus some more computations are required. Now let us discuss, step wise, the algorithm that specifies how to apply the partitioning (6) and (7) in a systematic manner to finally arrive at an optimum solution.

Let’s start with an initial lower bound for *z,* say *z ^{(0)}* at the first iteration, which is less than or equal to the optimal value

*z*.*This lower bound may be taken as the starting

*L*for some

_{j}*x*

_{j}.In addition to the lower bound z^{ (0)}, we also have a list of LPPs (to be called master list) differing only in the bounds (5). To start with (the 0^{th} iteration) the master list contains a single LPP consisting of (1), (2), (4) and (5). Let us now discuss the procedure that specifies how the partitioning (6) and (7) can be applied systematically to eventually get an optimum integer-valued solution.

1 | Rupesh

December 4, 2011 at 6:59 am

Dear Nikhat S Khan,

can u pls send me solution of MB0048 set-2 & MB0049 Set-2.

i hv to submit it within 1 week. i m very greatful for your co-operaion.

mail id is- nsn.rupesh.solanki@gmail.com

pls do the needful.

Regards

Rupesh

Nikhat S Khan

December 4, 2011 at 11:36 am

Refer these 2 links for solution of MB0048 set-2 & MB0049 Set-2 :-

https://nikhatshahin.wordpress.com/category/mba-smu/mba-2nd-semester/assignments/mb0048-operations-research-assignments/set-2-mb0048-operations-research-set-2/

https://nikhatshahin.wordpress.com/category/mba-smu/mba-2nd-semester/assignments/mb0049-project-management-assignments/set-2-mb0049-project-management-set-2/

Regards,

Nikhat