Integer programming is concerned with optimization problems in which some of the variables are required to take on discrete values. Rather than allow a variable to assume all real values in a given range, only predetermined discrete values within the range are permitted. In most cases, these values are the integers giving rise to the name of this class of models.

The integrality requirement underlies a wide variety of applications. There are many situations, such as distributing goods from warehouses to factories or finding the shortest path through a network, where the flow variables are logically required to be integer valued. In manufacturing, products are often indivisible so a production plan that calls for fractional output is not acceptable. There are also many situations that require logical decisions of the form yes/no, go/no go, assign/don’t assign. Clearly these are discrete decisions that when quantified allow only two values. They can be modeled with binary variables that assume values of zero or one. Designers faced with selecting from a finite set of alternatives, schedulers seeking the optimal sequence of activities, or transportation planners searching for the minimum cost routing of vehicles all face discrete decision problems.

When optimization models contain both integer and continuous variables they are referred to as mixed-integer programs. The power and usefulness of these models to represent real-world situations cannot be overstated, but along with modeling convenience comes substantial computational difficulty. Only relatively small problems containing integer variables can be solved to optimality in most cases. At first glance this might seem counterintuitive given our ability to solve huge linear programs. However, the discrete nature of the variables gives rise to a combinatorial explosion of possible solutions. In the worst case, a majority of these solutions must be enumerated before optimality can be confirmed. Consequently, when the number of integer variables in a problem gets large, solving a model to optimality becomes very difficult, if not impossible. Rather, heuristic methods that do not guarantee optimality must be used to find solutions.

We address in this section the process if modeling optimization problems with integer variables.