Integer Linear Programming Problem

An LP problem in which decision variables take only integer values is called an Integer linear programming (ILP) problem. In LP problem, decision variables are considered to be real numbers and non-negative values. Some problems need only integer values as decision variables, such as the number of people or the number of pieces. An LP problem, in which the decision variables include both integer values and real values, is called a mixed integer linear programming (MILP) problem.

In general, it takes more time to solve an ILP problem than an LP one. ILP problems are classified into three catagories, which are (i) pure integer programming problem: all variables are required to be integer, (ii) mixed integer programming problem: some variables are restricted to be integers; the others can take any value, and (iii) binary integer programming problem: all variables are restricted to be 0 or 1.

In general, it takes more time to solve an ILP problem than an LP one. Let us consider (11.3a)-( 11.3e) again, and assume that the decision variables are limited to integer values.

In an LP problem, at least one of the corner points is the optimum solution.

Figure 11.5: Feasible region of integer linear programming problem.

Therefore, we need check only the corner points to determine the optimum solution. However, in an ILP problem, we have to check every possible grid point in the feasible region to identify the optimum value of the objective function, as shown in Fig. 11.5. In Fig. 11.5, we need to check the value of the objective function of eight grid points, (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), and (0, 2). We find that the optimum solution is (0, 2), and that the maximum value of the objective function is 10.

In the following, we consider a large-scale ILP problem with a diagram.

Figure 11.6 shows that we need to find the values of the objective function by considering several grid points. The optimal solution is obtained at xi =210 and л'2 = 179; the optimal value is 1105. This problem takes more time than that of the problem mentioned in (11.4a)-(l 1.4e) to calculate the solution since we have to consider many more grid points than those in Fig. 11.5.

Figure 11.6: Constraints and feasible region of a large-scale ILP problem.