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.

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.

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

x_{j}= 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 x_{j} are *integer*
variables which must take one of two possible values (zero or one).

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

0.5x_{1} + 1.0x_{2} + 1.5x_{3} + 0.1x_{4}
<= 3.1 (year 1)

0.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
<= 2.5 (year 2)

0.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4 (year 3)

To maximise the total return - hence we have

maximise 0.2x_{1} + 0.3x_{2} + 0.5x_{3} + 0.1x_{4}

This gives us the complete IP which we write as

maximise 0.2x_{1} + 0.3x_{2} + 0.5x_{3} + 0.1x_{4}

subject to

0.5x_{1} + 1.0x_{2} + 1.5x_{3} + 0.1x_{4}
<= 3.1

0.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
<= 2.5

0.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4

x_{j} = 0 or 1 j=1,...,4

Note:

- in writing down the complete IP we include the information that x
_{j}= 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.2x
_{1}is zero if x_{1}=0 (as we want since no return from project 1 if we do not do it) and 0.2 if x_{1}=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.2x_{1}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:

0x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 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:

0x_{1} + 0x_{2} + 1.5x_{3} + 0.1x_{4}
<= 3.1 (year 1)

0.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
<= 2.5 (year 2)

0x_{1} + 0.2x_{2} + 0.3x_{3} + 0x_{4} <=
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:

0x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4 + 0.2x_{1}

where note that we have 0x_{1} 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
y_{1} (say) that is counted as return taken in the objective and
one part y_{2} (say) that is taken as return used for future capital
in year 3. Then amending our formulation we have

y_{1} + y_{2} = 0.2x_{1}

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

0x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4 + y_{2}

to account for the capital added in year 3

maximise y_{1} + 0.3x_{2} + 0.5x_{3} + 0.1x_{4}

to account for the return declared as profit.

Note here that y_{1} and y_{2} (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.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4 + 0.15x_{1}

**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 C_{12} and C_{23} (>=0) with C_{12}
being the capital carried forward from year 1 to year 2 and C_{23}
being the capital carried forward from year 2 to year 3. Then the constraints
of the problem become:

0.5x_{1} + 1.0x_{2} + 1.5x_{3} + 0.1x_{4}
<= 3.1 (year 1)

C_{12} = 0.25(3.1 - (0.5x_{1} + 1.0x_{2} + 1.5x_{3}
+ 0.1x_{4}))

0.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
<= 2.5 + C_{12} (year 2)

C_{23} = (2.5 + C_{12} - (0.3x_{1} + 0.8x_{2}
+ 1.5x_{3} + 0.4x_{4}))

0.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
<= 0.4 + C_{23} (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:

x_{1} + x_{2} <= 1

This allows us to do neither of the projects (x_{1} = x_{2}
= 0). If we wish to insist that we must do exactly one of these projects
we can use

x_{1} + x_{2} = 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.3x_{1} + 0.8x_{2} + 1.5x_{3} + 0.4x_{4}
+ 0.9y <= 2.5 (year 2)

0.2x_{1} + 0.2x_{2} + 0.3x_{3} + 0.1x_{4}
+ 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)

x_{1} + y <= 1

and the objective becomes

maximise 0.2x_{1} + 0.3x_{2} + 0.5x_{3} + 0.1x_{4}
+ 0.2y

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?