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

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
(y_{1}) and reinvesting it as available capital in year 3 (y_{2}).

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

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

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

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

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

capital used + unused capital = capital available

Note also here how we have introduced additional variables (C_{1}
and C_{2}) that make our task of formulating the problem easier.

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

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:

x_{3} + x_{4} <= 1

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

x_{3} + x_{4} = 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