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.

Integer programming tutorial class solution


The decisions that need to be made are of three types:

Hence let

Note here that we do not directly view the problem as one of deciding the year in which to permanently close down a mine. Instead we introduce a variable indicating the "state" of a mine in each year ('open' or closed). In part this is motivated by the fact that we will need to know this information when formulating the objective function (since we have to pay a royalty if a mine is 'open' in a certain year). In any event formulating an IP tends to be an iterative process and if we have made a mistake in defining variables we will encounter difficulties in formulating the constraints/objective. At that point we can redefine our variables and reformulate.


Reading through the question we try and express each of the constraints first in words and then in terms of the variables defined above.

w1j + w2j + w3j + w4j <= 3    j=1,2,3,4,5 
x1j <= 2w1j       j=1,...,5  
x2j <= 2.5w2j    j=1,...,5 
x3j <= 1.3w3j   j=1,...,5 
x4j <= 3w4j      j=1,...,5 

Note that these equations enforce x<=0 (i.e. x=0) if w=0 (i.e. not operated).

Considering year one as an example we need

(1.0x11+0.7x21+1.5x31+0.5x41)/(x11+x21+x31+x41) = 0.9 

i.e. rearranging to get a linear equation

1.0x11+0.7x21+1.5x31+0.5x41 = 0.9(x11+x21+x31+x41) 

Generalising this expression to year j we get

1.0x1j+0.7x2j+1.5x3j+0.5x4j = qj(x1j+x2j+x3j+x4j)    j=1,...,5 

where the qj are the desired qualities in year j and are known constants (q1 = 0.9, q2 = 0.8, q3 = 1.2, q4 = 0.6 and q5 = 1.0).


Presumably we wish to maximise profit and using profit = (revenue - cost) we have that in this case:

Revenue = £ generated from the sale of the ore and this, for year j, is given by

10(x1j+x2j+x3j+x4j)    (£m) 

Cost = £ paid out in royalties and this, for year j, is given by

(5y1j+4y2j+4y3j+5y4j)  (£m) 

Note that the royalty paid depends only upon whether a mine is still 'open' or not - not on whether it is operated or not. Hence profit for year j = revenue - cost, so total profit =

SUM{j=1 to 5}[10(x1j+x2j+x3j+x4j)-(5y1j+4y2j+4y3j+5y4j)] 

and it is this that we wish to maximise.

Although the above might seem satisfactory in fact we have missed out an entire set of constraints relating to the logical connection between the closure variables (the y variables) and the operation variables (the w variables).

Looking at the equations we have so far we see that we have no equation relating the y variables (for closure) to the w variables (for operation). Plainly we cannot operate a mine if it is closed and so

wij <= yij    i=1,...,4 j=1,...,5 

since if yij = 1 this constraint becomes wij <= 1 (which is perfectly valid) and if yij = 0 this constraint becomes wij <= 0 i.e. wij = 0 as required (no operation if closed).

In addition to the above constraints we need to ensure that once a mine is closed it remains closed. This condition can be represented by the constraint

yij <= yij-1    i=1,...,4 j=2,...,5 

which ensures that if a mine is closed in one year (year j-1) it will be closed in the next year (year j).


As with all formulations we have made a number of assumptions (explicitly or implicitly) e.g.