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/dont 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
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.