Integer programming

A linear programming problem is used to find the maximum or minimum of an objective function subject to some restrictions. These limitations are usually inequalities. When these limitations are satisfied, a workable solution is obtained. When one of these solutions is the maximum or the minimum according to the objective function, an optimal solution /

In many real-life situations, the decision variables may be required to be integers, since you have to find out the number of buses needed or the number of personnel needed to deploy, etc. These kinds of problems are called integer programming problems.

Integer programming problems cannot be solved using the Simplex method, they must be solved using the branch and bind 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. Therefore, the solution to the problem of linear programming of integers will fall on any of the horizontal or vertical lines within the feasible region. The feasible set is no longer convex and becomes very difficult to solve due to its non-convex integers.

There are several different types of methods used to solve integer linear programming problems. The most commonly used method is the branch and link method.

Branch and Bound involves relaxing the Integer constraints and solving the linear program using the graphical or simplex method. If after relaxing the integer constraints, all the decision variables turn out to be integers, then the set of solutions 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 bound and bifurcation technique by solving the original problem with a bounded integer value of the decision variable added to the set of restrictions. When solving this new set of problems, if you produce an optimal value with integer values, then there may be better values ​​and therefore other branches should be investigated. Finally, the solution must be chosen from one of the nodes of the branches visited, which is the maximum or the minimum. We have to repeatedly keep solving a linear relaxation of the problem with newer integer limits and look for the best possible solution in context. For a smaller integer programming problem, it may be better to use a graphical method to solve the problem.