Model Building in Mathematical Programming, 5th Edition

Chapter 8

Integer programming

8.1 Introduction

A surprisingly wide class of practical problems can be modelled using integer variables and linear constraints. Sometimes such a model consists solely of integer variables. That is a pure integer programming (PIP) model. More commonly, there are both conventional continuous variables together with integer variables present. Such a model is said to be a mixed integer programming (MIP) model.

The wide applicability of integer programming (IP) (sometimes known as discrete programming) as a method of modelling is not obvious. Clearly, we can think of situations where it is only meaningful to make integral quantities of certain goods, for example, cars, aeroplanes or houses, or use integral quantities of some resource, for example, employees. In these cases we might use an IP model instead of an LP model. Although such obvious applications of IP do occur they are not common. In fact, in such situations, it is often more desirable to use conventional LP and round off the optimal solution values to the nearest integers.

The obvious type of application described above obscures the real power of IP as a method of modelling. Most practical IP models restrict the integer variables to two values, 0 or 1. Such 0–1 variables are used to represent ‘yes or no’ decisions. Logical connections between such decisions can often be imposed using linear constraints. Such methods of modelling are described in the next chapters.

Before discussing the building ...