Integer Programming
K. L. Hoffman and M. Padberg, “Combinatorial and Integer Optimization,” in S. I. Gass and C. M. Harris, editors, Encyclopedia of Operations Research and Management Science, Centennial Edition, (Boston: Kluwer Academic Publishers, 2001), 94102.
Linear programming (LP) involves finding the optimal values for a set of decision variables that are constrained by a system of linear inequalities. The objective can be to minimize cost or maximize profit. Linear programming has a broad range of applications that includes planning production rates for a mix of products, blending gasoline and reducing trim loss when cutting large sheets of paper or steel. In these contexts the decision variables are continuous and the optimal solution must lie at a corner point of the feasible region formed by the system of linear inequalities. There are situations, however, in which the decision variables must assume only integer values. A regional manager deciding how many cars to have at each of her car rental locations knows that the solution must be integer. Planning the number of police officers to have on duty each hour of the day requires that the solution take on integer values. Problems of these types in which the decision domain is restricted to integer values are called integer programming (IP) problems. Problem contexts that involve both integer and continuous decision variables are termed mixedinteger programming. Another equivalent term often used is combinatorial optimization. Optimal scheduling and sequencing decisions are often formulated as IP problems.
General purpose IP problems are orders of magnitude more complex to solve than LP problems because the optimal solution need no longer be at a corner point. However, there are IP problems that have structures that facilitate the development of special purpose solution algorithms that are even faster to solve than comparably sized LP problems. Interestingly, there are classes of LP problems in which the matrix structure of the system of linear inequalities guarantees that the optimal solution to the LP problem will have all integer values. The Transportation Problem is in that class. The Transportation Problem involves minimizing the total cost of transporting supplies of a single product type from various locations (e.g., plants or warehouses) to a set of demand points (e.g., retail facilities). The decision variables are how much to ship from point A to point B and the constraints are the locationspecific available supplies and demand.
An especially powerful IP modeling concept is the use of integer decision variables that take on only the values of 0 or 1. These 01 decision variables, also called indicator variables, are used to describe yesno decisions. Should a facility be built at this location or not? Should the corporation invest in this project or not? The Assignment Problem is a specific example of using only 01 variables. The Assignment Problem involves assigning, for example, people (or machines) to a set of mutually exclusive set of jobs (or tasks) so as to minimize the total cost (or time) of completing these jobs. The decision variable takes on the value "1" if person a is assigned to do job 1 and equals 0 if he is not assigned to that job.
The Integer Programming student activity, case studies and homework summarized in this lesson activity are limited to 01 decision variables. An earlier activity, Manpower Planning at Pizza ? includes an extension that explores the issue of integer decision variables that are not restricted to 01 values. The examples in this activity include a) investment portfolio selection, b) dividing (assigning) a set of season tickets amongst a group of buyers, c) facility location problems and d) steel production planning.
Back to What is OR?
