Integer linear programming problems arise when trying to solve linear systems while specifying that all of the unknown variables must be integers, or whole numbers. Linear systems are sets of equations that describe a situation for which the programmer is attempting to find a solution. They usually consist of one equation that must be maximized or minimized and one or more restricting equation that put limits on unknown variables. For the system to be linear, each restriction must be a linear equation; that is, it must contain no instances of the unknown variable with exponents greater than one.
Regular linear systems may be solved easily using a computer. The program can identify a solution by finding the derivative and setting it equal to zero. It can then verify that the point is a maximum or minimum by checking its immediate neighborhood on the function. As long as the derivative is defined at each point along the function, the computer has only a limited number of possible solutions to check.
Linear programming becomes integer linear programming with the addition of the integer restriction. This means that the problem remains the same, but the answer must consist of integer values for the unknown values: they must be whole numbers. Sometimes, this means that the solution will be suboptimal compared to the case in which fractions are allowed; it is reflective, however, of the real world, in which items often come in discrete, indivisible units. This makes integer linear programming important for business applications, since firms want to maximize profits as much as possible but cannot choose to sell a fraction of a product.
Once the integer restrictions are in place, the problem of solving the linear system is NP-complete. This means that the time that is necessary for a computer to solve the system is indeterminate. With integer restrictions, computers cannot use the tool of the derivative because there is no guarantee that the zero point of the derivative will fall on an integer. The solution will be the integer with the highest or lowest value out of all the integers, so the computer would have to check them all — a process that could take an infinite amount of time.
Programmers have developed heuristics, or methods of problem-solving, to deal with the complexity of these problems. One method of solving integer linear programming problems is the branch and bound algorithm, in which the computer solves a series of problems related to the original one to narrow down the available range of values to one solution. For complex problems, however, this can take a long time.
