|
Branch and Bound method Steps (Rule)
|
|
Step-1:
|
Solve the given problem using Simplex (BigM) method or Graphical method
|
|
Step-2:
|
If optimal integer solution found then stop the procedure. Otherwise, goto Step-3.
|
|
Step-3:
|
Branch Step
a. Let `x_k` be the variable which does have not integer value. (If more than one such variable then select the largest fractional value or choose any variable arbitrarily)
b. Now branch the Problem-A into 2 sub problems B and C.
Sub-problem B: `x_k <= [x_k]`
Max `Z = c_j x_j`
Subject to `ax <= b`
`x_k <= [x_k]`
and all `x_j >= 0`
|
Sub-problem C: `x_k >= [x_k] + 1`
Max `Z = c_j x_j`
Subject to `ax <= b`
`x_k >= [x_k] + 1`
and all `x_j >= 0`
|
Here `[x_k]` is the integer value of `x_k`
|
|
Step-5:
|
Bound Step
Find the optimal solution of subproblem B and C. Let optimal value of subproblem B be `Z_B` and optimal value of subproblem C be `Z_C`. Let the lower bound be `Z_L`.
|
|
Step-5:
|
Examine the solution of subproblem B and C.
a. If solution is infeasible then terminate this branch.
b. If solution is feasible but not integer then.
1. objective function value greater than the lower bound, then goto step-2.
2. objective function value less than the lower bound, then terminate this branch.
c. If solution is feasible integer solution.
1. If objective function value = upper bound, an optimal solution has been reached and terminate the problem.
2. If objective function value `!=` upper bound,
2.1 but greater than the lower bound, then this value is considered as new upper bound and goto step-2.
2.2 but less than the lower bound, then terminate this branch.
|
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
