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

Variables

We need to decide whether to use an investment opportunity or not so let x_j = 1 if we use investment opportunity j (j=1,...,10), 0 otherwise

Constraints

• total amount of capital available for these investments is Q

SUM{j=1,...,10}C_jx_j <= Q

• investment opportunities 3 and 4 are mutually exclusive and so are 5 and 6

x₃ + x₄ <= 1
x₅ + x₆ <= 1

• neither 5 nor 6 can be undertaken unless either 3 or 4 is undertaken

x₅ <= x₃+ x₄
x₆ <= x₃+ x₄

• at least two and at most four investment opportunities have to be undertaken from the set {1,2,7,8,9,10}

2 <= x₁ + x₂ + x₇ + x₈ + x₉ + x₁₀ <= 4

Objective

The objective is to maximise the total estimated long-run profit i.e.

maximise SUM{j=1,...,10}P_jx_j

Note here that sometimes it is possible to correctly represent the problem, but using different constraints. For example for this problem we could replace

x₅ <= x₃+ x₄
x₆ <= x₃+ x₄

by the single constraint

x₅ + x₆ <= x₃+ x₄

since we have x₅ + x₆ <= 1

Solution

The network diagram is shown below. Note the introduction of a dummy activity I with a duration of zero to represent the end of the project.

Let E_i represent the earliest start time for activity i such that all its preceding activities have been finished. We calculate the values of the E_i (i=A,B,...,I) by going forward, from left to right, in the network diagram.

To ease the notation let T_i be the activity completion time associated with activity i (e.g. T_B = 3). Then the E_i are given by:

E_A = 0 (assuming we start at time zero)
E_B = 0 (assuming we start at time zero)
E_C = E_A + T_A = 0 + 2 =2
E_D = max[E_A + T_A, E_B + T_B] = max[0 + 2, 0 + 3] = 3
E_E = max[E_C + T_C, E_D + T_D] = max[2 + 4, 3 + 3] = 6
E_F = E_C + T_C = 2 + 4 = 6
E_G = E_E + T_E = 6 + 8 = 14
E_H = max[E_F + T_F, E_G + T_G] =max[6 + 3, 14 + 2] = 16
E_I = E_H + T_H = 16 + 3 = 19

Hence the minimum possible completion time for the entire project is 19 weeks i.e. 19 (weeks) is the minimum time needed to complete all the activities.

We now need to calculate the latest times for each activity.

Let L_i represent the latest start time we can start activity i and still complete the project in the minimum overall completion time. We calculate the values of the L_i (i=A,B,...,I) by going backward, from right to left, in the network diagram. Hence:

L_I = 19
L_H= L_I - T_H = 19 - 3 = 16
L_G = L_H - T_G = 16 - 2 = 14
L_F = L_H - T_F = 16 - 3 = 13
L_E = L_G - T_E = 14 - 8 = 6
L_D = L_E - T_D = 6 - 3 = 3
L_C = min[L_E - T_C, L_F - T_C] = min[6 - 4, 13 - 4] = 2
L_B = L_D - T_B = 3 - 3 = 0
L_A = min[L_C - T_A, L_D - T_A] = min[2 - 2, 3 - 2] = 0

Note that as a check all latest times are >=0 at least one activity has a latest start time value of zero.

As we know the earliest start time E_i, and latest start time L_i, for each activity i it is clear that the amount of slack or float time F_i available is given by F_i = L_i - E_i which is the amount by which we can increase the time taken to complete activity i without changing (increasing) the overall project completion time. Hence we can form the table below:

Activity   Li          Ei           Float Fi 
A          0           0             0
B          0           0             0
C          2           2             0
D          3           3             0
E          6           6             0
F         13           6             7
G         14          14             0
H         16          16             0

Any activity with a float of zero is critical. Note here that, as a check, all float values should be >= 0.

Hence the critical activities are A,B,C,D, E,G and H and the float for the only non-critical activity F is 7 weeks.

In order to formulate the problem of deciding the completion time for C, D and E so as to ensure that the project is completed within 17 weeks we make use of integer programming.

Let the x variables (suitably subscripted) represent feasible start times for each activity (>=0 and integer). Note here that we deal with feasible start times in formulating this program rather than (as above) with earliest start times.

Introduce zero-one variables:
C_i = 1 if a completion time of i (i=4,3,2,1) is chosen for activity C, 0 otherwise
D_i = 1 if a completion time of i (i=3,2,1) is chosen for activity D, 0 otherwise
E_i = 1 if a completion time of i (i=8,7,6) is chosen for activity E, 0 otherwise

then the constraints relating to the choice of completion time are:

C₄ + C₃ + C₂ + C₁ =1
D₃ + D₂ + D₁ = 1
E₈ + E₇ + E₆ = 1

i.e. exactly one completion time must be chosen for C, D and E respectively.

The constraints relating to the network logic are:

x_C >= x_A + 2
x_D >= x_B + 3
x_D > = x_A + 2
x_E >= x_C + 4C₄ + 3C₃ + 2C₂ +1C₁

where 4C₄ + 3C₃ + 2C₂ +1C₁ is the completion time for activity C (remember C₄, C₃, C₂ and C₁ are zero-one variables).

x_E >= x_D + 3D₃ + 2D₂ +1D₁
x_F >= x_C + 4C₄ + 3C₃ + 2C₂ +1C₁
x_G >= x_E + 8E₈ + 7E₇ + 6E₆
x_H >= x_F + 3
x_H >= x_G + 2
x_I >= x_H +3

x_I <= 17 (to complete within 17 weeks)

and the objective is:

minimise 3C₄ + 7C₃ + 10C₂ +15C₁ + 12D₃ + 16D₂ +25D₁ + 5E₈ + 9E₇ +14E₆

Note here that essentially in this question we have extended cost/time tradeoff which we considered before from involving a linear assumption to the situation we we can have a diverse range of possible completion times, and any associated costs we wish.