Reduced Feasible Region and Bounds For Improved Efficiency of the Branch and Bound Method of Linear Integer Programming
Published: 2011
Author(s) Name: Elias Munapo, Santosh Kumar and Lutfar Khan
Locked
Subscribed
Available for All
Abstract
This paper develops a strategy to reduce the feasible
space containing the optimal integer solution of a linear
integer-programming model before applying the
branch and bound method of integer programming.
The strategy improves efficiency of the branch and
bound method. It also calculates upper and lower
bounds for the optimal solution. A ratio using a factor
of 1.5 has been used to calculate the reduction in the
objective function, with the hope that the reduced
feasible space contains the optimal solution. This ratio
of 1.5 has been tested on 200 randomly generated
integer models. The procedure of decreasing the
objective Z value also helps in computing the variable
ranges. With the use of variable ranges and convex
feasible space reduction, the optimal integer solution
can be searched efficiently by using the branch and
bound approach.
View PDF