Learning Curve…

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

Posted on: October 3, 2011

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)

xj is integer valued , j = 1, 2, …….., r (< n) –––––––––––––––––- (3)

xj > 0 …………………. j = r + 1, …….., n ––––––-––––––––––––––– (4)

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

Lj ≤ xj ≤ Uj j = 1, 2, …. r –––––––––––––––––––––––––– (5)

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

Consider any variable xj, and let I be some integer value satisfying Lj £ I £ Uj – 1. Then clearly an optimum solution (1) through (5) also satisfies either linear constraint.

x j ³ I + 1 –––––––––––––––––––––––––––––– (6)

Or the linear constraint xj ≤ 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 x1 = 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 ≤ x1 ≤ U1 in one problem and L1 ≤ x1 ≤ 1 in the other. Further to each of these problems, process an optimal solution satisfying integer constraint (3).

Then 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 Lj for some xj.

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 0th 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.

Advertisements

2 Responses to "MB0048 : What are the meaning and role of the lower bound and upper bound in the branch and bound method?"

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Author

Learning days (Calendar)

October 2011
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

Knowledge Bank (Archives)

I am on Twitter

Blog Stats

  • 503,999 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 43 other followers

%d bloggers like this: