Integer Linear Programming (ILP) is required to solve optimization problems with integer values as the solution.
Integer Linear Programming is a subset of Linear Programming (LP). It has all the characteristics of an LP, an attempt to find a maximum or minimum solution to a function given certain constraints, except for some or all of the variables to the LP solution must be restricted to integers.
There are many events we need to solve the real world optimization problems with Integer Linear Programming, instead of Linear Programming. It doesn't make sense to use a continuous variable to represent the number of airplanes to produce because there is no point in manufacturing a partial airplane. The production of large indivisible items is one of the use case of ILP.
We showed how to load boxes to a set of lorries in our previous article Graphical Method for Integer Linear Programming (ILP), in which we cannot rent a partial lorry (7.5 lorries). It has to be a whole lorry (7 or 8 lorries), leaving the empty space unoccupied.
The variables take only integer values, instead of a solid area of feasible region. The optimal solution is always on the edge of the feasible region, however, rounding off the floating point solution can lead to infeasible solution.
So, the integer solution may not lie on an extreme point of continuous feasible region, and LP cannot be used. From the graphic, the collection of dots/points indicate the new feasible solutions.
Types of Integer Programming
According to the nature of the variables, we can distinguish three types of IP models, which are Pure IP, Mixed IP and Binary IP.
Pure IP requires that all decision variables have integer values in the final solution.
Mixed IP requires some, not all, of the decision variables to have integer solutions.
Binary IP, also 0-1 IP, involves problems in which the variables are restricted to be either 0 or 1, such as state or mode decisions, yes/no decisions or logical decisions.
Example:
Unit commitment problem with the state or mode decisions. A particular stage 0-1 binary variables (boolean), i.e. on or off.
Planning of investments as a yes/no decisions. It takes a value 1 to invest in a warehouse (yes) and 0 to ignore it (no).
A given tax break is only applicable (true/false) if a certain investment is made. This is a logical decisions, the logic constraints between different decision variables, i.e. AND, OR, NOT, IMPLY, ... etc.
The solution complexity increases with the number of possible combinations of integer variables (combinatorial problem). Even the fastest computer can take excessively long time to solve a big integer programming problem.
Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
There are some methods for solving ILP problems, such as:
Rounding off a non-integer solution
Cutting Plane method
Branch and Bound method
The addictive algorithm for 0-1 IP
which we will explain in details in the coming lessons.
