A linear programming problem is used to find either the maximum or minimum of an objective function subject to some constraints. These constraints are usually inequalities. When these constraints are satisfied one obtains a feasible solution. When one of these solutions is either the maximum or the minimum as per what the objective function, one gets an optimum solution/
In many real life situations one may require that the decision variables be integer as one has to find out number of buses required or no of staff required to be deployed etc., Such classes of problems are called as Integer Programming problems.
Integer programming problems cannot be solved using the Simplex method, they need to be solved by using the branch and bound method. One can imagine the feasible region enclosed by the constraints in a convex optimization problem with horizontal and vertical lines drawn at each integer point. The solution to the Integer Linear Programming problem will hence fall on any of the horizontal or vertical lines inside the feasible region. The feasible set is no longer convex and becomes very arduous to solve due to is non convex nature.
There are several different types of methods used to solve Integer Linear Programming problems. The most commonly used method is the branch and bound method.
Branch and Bound involves relaxing the Integer constraints and solving the linear program using either the graphical or the simplex method. If after relaxing the integer constraints, all the decision variables turn out to be integers, then the solution set is correct.
However if the solution to the relaxed linear program does not yield integer values as solutions of the decision variables one has to employ a branch and bound technique by solving the original problem with a bounded integer value of the decision variable added to the set of constraints. When this new problem set is solved, if it yields an optimum value with integer values, then there may be better values and so other branches have to be investigated. Eventually the solution has to be picked from one of the nodes in the branches visited which is either the maximum or the minimum. We have to keep repetitively solving a linear relaxation of the problem with newer integer bounds and check for the best possible solution in the context. For a lower dimensional Integer Programming problem it may be better to use a graphical method to solve the problem.
An extension of the Integer Programming problem is the 0-1 integer programming problem where decision variables can take only 0 or 1. These kind of problems are especially useful to solve problems similar to the knap sack problem.
Post a Comment