# OR-Notes

## J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

#### Network analysis - integer programming

When we dealt with network analysis previously we were concerned with just a single project, where the implicit assumption was that we had already decided to do the project. Suppose now that we are considering four possible projects, which each run for 3 years and have the following characteristics:

```                         Capital requirements (£m)
Project   Return (£m)    Year   1     2     3
1         0.2                   0.5   0.3   0.2
2         0.3                   1.0   0.8   0.2
3         0.5                   1.5   1.5   0.3
4         0.1                   0.1   0.4   0.1
Available capital (£m)          3.1   2.5   0.4
```

We have a decision problem here: Which projects would you choose in order to maximise the total return?

Note here that, from the project management viewpoint, the focus has moved from the tactical consideration of how to organise the project which we considered previously under network analysis (cost/time tradeoff, uncertain activity completion times, resource restrictions, etc) to a more strategic viewpoint.

This problem can be formulated and solved as an integer programming problem. Such problems arise when (as we shall see below) the variables in the formulation of the problem must take integer (discrete) values. Problems in which this is the case are called integer programs (IP's) and the subject of solving such programs is called integer programming (also referred to by the initials IP).

IP's occur frequently because many decisions are essentially discrete (such as yes/no, go/no-go) in that one (or more) options must be chosen from a finite set of alternatives.

Note here that problems in which some variables can take only integer values and some variables can take fractional values are called mixed-integer programs (MIP's).

Solution

In order to solve our project selection example we follow the same approach as we used for formulating LP's - namely:

• variables
• constraints
• objective.

We do this below and note here that the only significant change in formulating IP's as opposed to formulating LP's is in the definition of the variables.

#### Variables

Here we are trying to decide whether to undertake a project or not (a "go/no-go" decision). One "trick" in formulating IP's is to introduce variables which take the integer values 0 or 1 and represent binary decisions (e.g. do a project or not do a project) with typically:

• the positive decision (do something) being represented by the value 1; and
• the negative decision (do nothing) being represented by the value 0.

Such variables are often called zero-one or binary variables

To define the variables we use the verbal description of

```xj = 1 if we decide to do project j (j=1,...,4)
= 0 otherwise, i.e. not do project j (j=1,...,4)
```

Note here that, by definition, the xj are integer variables which must take one of two possible values (zero or one).

#### Constraints

The constraints relating to the availability of capital funds each year are

0.5x1 + 1.0x2 + 1.5x3 + 0.1x4 <= 3.1 (year 1)
0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 <= 2.5 (year 2)
0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4 (year 3)

#### Objective

To maximise the total return - hence we have

maximise 0.2x1 + 0.3x2 + 0.5x3 + 0.1x4

This gives us the complete IP which we write as

maximise 0.2x1 + 0.3x2 + 0.5x3 + 0.1x4

subject to

0.5x1 + 1.0x2 + 1.5x3 + 0.1x4 <= 3.1
0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 <= 2.5
0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4
xj = 0 or 1 j=1,...,4

Note:

• in writing down the complete IP we include the information that xj = 0 or 1 (j=1,...,4) as a reminder that the variables are integers
• you see the usefulness of defining the variables to take zero/one values - e.g. in the objective the term 0.2x1 is zero if x1=0 (as we want since no return from project 1 if we do not do it) and 0.2 if x1=1 (again as we want since get a return of 0.2 if we do project 1). Hence effectively the zero-one nature of the decision variable means that we always capture in the single term 0.2x1 what happens both when we do the project and when we don't do the project.
• you will note that the objective and constraints are linear (i.e. any term in the constraints/objective is either a constant or a constant multiplied by an unknown). In this course we deal only with linear integer programs (IP's with a linear objective and linear constraints). It is plain though that there do exist nonlinear integer programs - these are, however, outside the scope of this course.

Extensions to this basic problem include:

• projects of different lengths
• projects with different start/end dates
• adding capital inflows from completed projects
• projects with staged returns
• carrying capital forward from year to year
• mutually exclusive projects (can have one or the other but not both)
• projects with a time window for the start time.

We shall consider these extensions below.

Extensions

• projects of different lengths

Projects with different lengths are easily dealt with, just set their capital requirement in any year in which the project does not exist (i.e. has not started or has already ended) to zero. For example if project 1 only runs for 2 years (instead of 3 years) and hence finishes in year 2 then the capital requirement constraint for year 3 becomes:

0x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4

• projects with different start/end dates

Projects with different start/end dates are dealt with in a similar manner as projects of different lengths, just set their capital requirements in any year in which they do not exist (i.e. they have not started or have already ended) to zero. For example if project 1 starts and ends in year 2; project 2 starts in year 2 and project 4 ends in year 2 then the capital requirement constraints become:

0x1 + 0x2 + 1.5x3 + 0.1x4 <= 3.1 (year 1)
0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 <= 2.5 (year 2)
0x1 + 0.2x2 + 0.3x3 + 0x4 <= 0.4 (year 3)

• adding capital inflows from completed projects

If project 1 finishes in year 2, and all of the return from project 1 is available as capital in year 3 then this can be formulated by changing the capital requirement constraint for year 3 to:

0x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4 + 0.2x1

where note that we have 0x1 above as project 1 finishes in year 2 and hence has no capital requirement in year 3.

A question arises here in that if we put the return from a project into the capital for future years then should we be counting the return from the project in the objective function as well? One way to address this for project 1 here is to say that the return is split into two - one part y1 (say) that is counted as return taken in the objective and one part y2 (say) that is taken as return used for future capital in year 3. Then amending our formulation we have

y1 + y2 = 0.2x1

a balancing equality equation to correctly account for the return (since we may choose not to do project 1)

0x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4 + y2

to account for the capital added in year 3

maximise y1 + 0.3x2 + 0.5x3 + 0.1x4

to account for the return declared as profit.

Note here that y1 and y2 (both >=0) are continuous (fractional) variables so adding them in this way means that we have a mixed-integer program (MIP).

• projects with staged returns

In this extension we have that a project gives a return at various stages over its lifetime, and this return can (perhaps) be used as capital to fund ongoing (or new) projects. To illustrate how this can be formulated consider project 1 which gives a total return of 0.2. Suppose now that this project gives a return of 0.15 at the end of year 2, and the remaining return of 0.05 in year 3. Suppose further that all of this "early" return can be used as available capital in year 3. Then the capital requirement constraint in year 3 becomes:

0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4 + 0.15x1

• carrying capital forward from year to year

In the example as currently formulated we have capital available in each year (3.1 in year 1, 2.5 in year 2 and 0.4 in year 3). In any particular year all of this capital may not be consumed by the projects that we choose to do. Suppose that we are allowed to carry forward (from year to year) 25% of any capital that is unused. To formulate this introduce linear (fractional) variables C12 and C23 (>=0) with C12 being the capital carried forward from year 1 to year 2 and C23 being the capital carried forward from year 2 to year 3. Then the constraints of the problem become:

0.5x1 + 1.0x2 + 1.5x3 + 0.1x4 <= 3.1 (year 1)
C12 = 0.25(3.1 - (0.5x1 + 1.0x2 + 1.5x3 + 0.1x4))
0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 <= 2.5 + C12 (year 2)
C23 = (2.5 + C12 - (0.3x1 + 0.8x2 + 1.5x3 + 0.4x4))
0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 <= 0.4 + C23 (year 3)

• mutually exclusive projects (can have one or the other but not both)

Suppose that projects 1 and 2 are mutually exclusive, i.e. we can choose to do one, or other, of these projects but not both. Then this can be formulated by adding to the problem the constraint:

x1 + x2 <= 1

This allows us to do neither of the projects (x1 = x2 = 0). If we wish to insist that we must do exactly one of these projects we can use

x1 + x2 = 1

• projects with a time window for the start time

Suppose that project 1 can start either in year 1, when it has the characteristics given above, or in year 2, when it has different characteristics - still the same return of 0.2 but a capital requirement of 0.9 in year 2 and 0.4 in year 3. Then this can be formulated by introducing a new zero-one variable y with y=1 representing choosing to do project 1 starting in year 2, y=0 representing not choosing to do project 1 starting in year 2. Then the capital requirement constraints for years 2 and 3 become:

0.3x1 + 0.8x2 + 1.5x3 + 0.4x4 + 0.9y <= 2.5 (year 2)
0.2x1 + 0.2x2 + 0.3x3 + 0.1x4 + 0.4y <= 0.4 (year 3)

We also need to add a constraint to prevent project 1 being started at more than one start time (i.e. project 1 starting in year 1 and project 1 starting in year 2 are mutually exclusive)

x1 + y <= 1

and the objective becomes

maximise 0.2x1 + 0.3x2 + 0.5x3 + 0.1x4 + 0.2y

#### Solving the problem

Here we shall just use the package to solve our simple project selection problem. If you wish to learn more about formulating and solving integer programs see here.

The package input for the problem presented above is given below.

with the solution being shown below.

Here we can see that the optimal decision is to choose to do projects 3 and 4.

Note that one advantage of formulating the problem in this structured manner (as a decision model, using variables, constraints and objective) is that we can investigate sensitivity very easily. For example you can see that in the above numeric solution we have chosen to do projects 3 and 4. This in fact means that we have spare capital available in years 1 and 2, but that all of our capital in year 3 is utilised. Suppose therefore (since all projects give a positive return) we wish to argue to higher management for this capacity constraint of 0.4 to be raised - how might you use the model you have developed to make your case for this capacity constraint to be raised?