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 tutorial question

A project manager in a company is considering a portfolio of 10 large project investments. These investments differ in the estimated long-run profit (net present value) they will generate as well as in the amount of capital required.

Let Pj and Cj denote the estimated profit and capital required (both given in units of millions of £) for investment opportunity j (j=1,...,10) respectively. The total amount of capital available for these investments is Q (in units of millions of £).

Investment opportunities 3 and 4 are mutually exclusive and so are 5 and 6. Furthermore, neither 5 nor 6 can be undertaken unless either 3 or 4 is undertaken. At least two and at most four investment opportunities have to be undertaken from the set {1,2,7,8,9,10}.

The project manager wishes to select the combination of project investments that will maximise the total estimated long-run profit subject to the restrictions described above.

Formulate this problem as an integer program.

The table below defines the activities within a small project.

        Activity        Completion time        Immediate predecessor
                        (weeks)                 activities
            A               2                      - 
            B               3                      -
            C               4                      A
            D               3                      B,A
            E               8                      D,C
            F               3                      C
            G               2                      E
            H               3                      F,G

In the above network there are a number of options for the completion time for activities C, D and E as shown below:

          Activity     Completion time    Cost (£'000)
             C                4               3
                              3               7
                              2               10
                              1               15
             D                3               12
                              2               16
                              1               25
             E                8               5
                              7               9
                              6               14

For example choosing a completion time for activity E of 6 weeks costs £14,000.