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, as the number of buses needed or the personnel needed to deploy, etc. have to be figured out. These kinds of problems are called integer programming problems.

Integer programming problems cannot be solved by the Simplex method, they must be solved by 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 whole linear programming problem will lie 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 nature.

There are several different types of methods that are used to solve integer linear programming problems. The most widely used method is the branch and bind 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 of 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 limitations. When solving this new set of problems, if you return 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 visited branches, 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.

An extension of the integer programming problem is the 0-1 integer programming problem where decision variables can take only 0 or 1. These types of problems are especially useful for solving problems similar to the knap sack problem.