Optimization of Integer Programming using Branch and Bound Method
A linear program with decision variables restricted to integer values is called a linear integer program.
There are three basic types of integer linear programming models:
Total integer model, all the decision variables are required to have integer values. X1=2, X2=3 and X3=0
0 / 1 integer model, all the decision variables have integer values of zero or one.
X1=1, X2=0 and X3=1
Mixed integer model, some of the decision variables (but not all) are required to have integer values.
X1=2, X2=3 and X3=1.5
In practice, mainly the variable of interest have to be integers.Example: number of laptop, printer, human being…etc.
In the above cases fractional values do not make any sense in practice.
Rounding-off these values to the nearest integers is a must.
Rounding-off may result in sub-optimal or infeasible solutions.
Solutions are feasible, the objective function may not be optimal.
The branch and bound method is a solution approach that partitions the feasible solution space into smaller subsets of solutions.
A linear programming model solution with no integer restrictions is called a relaxed solution.
The optimal solution will always be between the upper bound of the relaxed solution and a lower bound of the rounded down integer solution.
Steps in Branch and Bound Method
1. Find the optimal solution to the LP model with the integer restriction relaxed.
2. The relaxed solution be the upper bound & the rounded-down integer solution be the lower bound.
3. Select the greatest fractional part for branching. Create two new constraints for this variable. The result will be a new ≤ constraint and a new ≥ constraint.
4. Create two new nodes, one for the ≥ constraint and one for the ≤ constraint.
5. Solve the relaxed LP model with the new constraint added at each of these nodes.
6. The relaxed solution is the upper bound at each node, and the existing maximum integer solution (at any node) is the lower bound.
7. If the process produces a feasible integer solution with the greatest upper bound value of any ending node, the optimal integer solution has been reached. If a feasible integer solution does not emerge, branch from the node with the greatest upper bound.
8. Return to step 3.
