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.

Extensions

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 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)

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).

If we were to solve this MIP numerically then we would find the optimal split between taking the return from project 1 as return in the objective (y1) and reinvesting it as available capital in year 3 (y2).

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

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 C1 and C2 (>=0) with C1 being the unused capital in year 1 and C2 being the unused capital in year 2. Then the constraints of the problem become:

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

Note here that in years 1 and 2 we have made use of the equality relationship:

Note also here how we have introduced additional variables (C1 and C2) that make our task of formulating the problem easier.

Suppose that projects 3 and 4 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:

x3 + x4 <= 1

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

x3 + x4 = 1

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