BINARY linear programming

binary-programminglinear programmingoptimization

Hi please can someone help me with this problem.

(OS) has acquired a plot of land on which it proposes to build three office blocks, Alpha, Beta and Gamma. Alpha and Beta will take two years to build and Gamma will take three years. The planning consent stipulates that all the buildings must be complete within 5 years of beginning construction. OS has 60 skilled workers available. Alpha requires 50 workers at all times, Beta 20 and Gamma 30. When complete Alpha and Gamma will attract an annual rent of £50,000, and Beta £30,000. Construct a Binary Integer Programme to identify in which year OS should begin each building and the maximum rental revenue it can achieve to offset its costs over the five- year construction period.

I thought there should be 11 decision variables but I am not sure how to approach the problem. I have started by saying let x1 be the year 1 alpha will start building, x2 be year 2 alpha will start building, x3 be year 3 alpha will start building, x4 be year 4 alpha starts building, x5 be year 1 beta will start, x6 year 2 beta, x7 year 3 beta, x8 year 4 beta, x9 year 1 gamma, x10 year 2 gamma and x11 year 3 gamma. I don't understand how to do the constraints and put it into solver on excel? I can't figure out the constraints, I was thinking it maybe be like x1+x2+x3+x4 =50 x5+x6+x7+x8 = 20 x9+x10+x11 = 30 I know the decision variables need to be binary on Excel

Any help would be appreciated Thanks in advance

Best Answer

I have tackled your problem with the MiniZinc constraint solver:

set of int: years = 1..5;

array[years] of var bool: a;
array[years] of var bool: b;
array[years] of var bool: c;

% Limitation of workers
% Sum of workers must not exceed 60 for any year
constraint forall(y in years) (
  60 >= (50*a[y] + 20*b[y] + 30*c[y])
);

% working durations are modelled as sums of slots
constraint sum([a[y] | y in years]) == 2;
constraint sum([b[y] | y in years]) == 2;
constraint sum([c[y] | y in years]) == 3;

% no gaps allowed; working slots must be adjacent
% shorthand: 
% constraint exists([a[y] /\ a[y+1] | y in 1..4]);
constraint (a[1] /\ a[2]) \/
           (a[2] /\ a[3]) \/
           (a[3] /\ a[4]) \/
           (a[4] /\ a[5]);

constraint (b[1] /\ b[2]) \/
           (b[2] /\ b[3]) \/
           (b[3] /\ b[4]) \/
           (b[4] /\ b[5]);

% shorthand: 
% constraint exists([c[y] /\ c[y+1] /\ c[y+2] | y in 1..3]);
constraint (c[1] /\ c[2] /\ c[3]) \/
           (c[2] /\ c[3] /\ c[4]) \/
           (c[3] /\ c[4] /\ c[5]);

% sum of revenues; binary true is translated to one, false to zero
solve maximize (not a[5]) * (50000 + (not a[4]) * (50000 + (not a[3]) * 50000)) +
               (not b[5]) * (30000 + (not b[4]) * (30000 + (not b[3]) * 30000)) +
               (not c[5]) * (50000 + (not c[4]) * 50000);

output ["\n"] ++ [ if show(a[y]) == "true" then " a " else "   " endif | y in years ] ++
       ["\n"] ++ [ if show(b[y]) == "true" then " b " else "   " endif | y in years ] ++
       ["\n"] ++ [ if show(c[y]) == "true" then " c " else "   " endif | y in years ];

There are three times five binary decision variables. Each describes if or if not a given building is being worked on during a given year.

The resulting output:

          a  a 
 b  b          
 c  c  c

What remains to be done is to translate the constraints into equations and inequalities:

Worker constraints:
50*a1 + 20*b1 + 30*c1 <= 60
50*a2 + 20*b2 + 30*c2 <= 60
50*a3 + 20*b3 + 30*c3 <= 60
50*a4 + 20*b4 + 30*c4 <= 60
50*a5 + 20*b5 + 30*c5 <= 60

Duration constraints:
a1 + a2 + a3 + a4 + a5 = 2
b1 + b2 + b3 + b4 + b5 = 2
c1 + c2 + c3 + c4 + c5 = 3

Gap constraints:
a1 * a2 + a2 * a3 + a3 * a4 + a4 * a5 > 0
b1 * b2 + b2 * b3 + b3 * b4 + b4 * b5 > 0
c1 * c2 * c3 + c2 * c3 * c4 + c3 * c4 * c5 > 0

Objective:
50000 * (1 - a5) * (1 + (1 - a4) * (1 - a3)) +
30000 * (1 - b5) * (1 + (1 - b4) * (1 - b3)) +
50000 * (1 - c5) * (2 - c4)

I have not been able to solve this with Excel.

Related Question