5.1 Introduction

So far we have been concerned with Linear Programming. In this all the constraints are linear and the decision variables are continuous, i.e. they can take any value between their lower bounds (most often, zero) and their upper bounds. We shall now see what happens when we lift the restriction that decision variables must be continuous, and, in particular, permit them to take values which are integer, i.e. 0, 1, 2, ... .

Why should we want to do this? One reason is to represent decisions where we must use some material in "lumpy" quantities, for instance how many bags of each material we should load into the hopper when making up animal feed. But this is actually a minor use of integer decision variables. The main uses are to represent:

  • "yes-no" decisions; we represent these by the values 1 and 0. Decision variables which take only these values are known as binary variables;
  • selection of one option from many; these can be represented by a series of binary variables, but it is better to use a more advanced structure, the Special Ordered Set of Type 1;
  • piecewise-linear functions of a decision variable; sometimes these can be represented without needing to use integer programming; at other times they are most efficiently represented by using Special Ordered Sets of Type 2.

Integer Programming (IP) thus provides a powerful technique for tackling problems which have a mixture of continuous and discrete activities, including those involving scheduling.

Unlike Linear Programming, IP is not a "black box" technique. You cannot simply define the mathematical formulation and hand the problem over to the IP code to find the optimal solution. There are ways of specifying a problem which will work and ways which will not. Some of the standard rules which apply to LPs, such as keeping the size of the problem to a minimum, no longer apply. That is, although you should still try to keep the complexity of the problem to a minimum, it can pay to add extra rows and columns to make the formulation "tighter".

Even when you have specified your problem in a good way, you should not expect to hand it over to the IP code and wait for it to produce the answer. To be sure, this is what you do the first time that you run it, and the IP code may produce an answer quickly. But you will often have to experiment with the IP code and the formulation of your problem to find a good way of solving it.

This lecture starts by exploring what IP is good at and what it finds difficult. Next the building blocks of integer programming - integer variables, special ordered sets, etc - are introduced and demonstrated with examples. There follows a discussion of how integer programming codes work and tactics which can be used to assist in finding solutions. Finally there is a survey of more advanced techniques which are used to tackle difficult IP problems.

previous contents next