/* CPP, Critical Path Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* Note: Reduced costs of auxiliary variables phi[j,k] (see below)
         can be only zero or one. The critical path is defined by the
         constraints, whose reduced cost is one. */

set J;
/* set of jobs (activities) */

set P{j in J}, in J, default {};
/* P[j] is a subset of jobs that immediately precede job j */

param t{j in J}, >= 0;
/* duration required to perform job j */

var x{j in J}, >= 0;
/* starting time of job j */

s.t. phi{j in J, k in P[j]}: x[j] >= x[k] + t[k];
/* job j can start only after all immediately preceding jobs have been
   completely performed */

var z;
/* project makespan */

s.t. fin{j in J}: z >= x[j] + t[j];
/* which is the maximum of the completion times of all the jobs */

minimize obj: z;
/* the objective is make z as small as possible */

data;

/* The optimal solution is 46 */

param : J :  t :=
        A    3    /* Excavate */
        B    4    /* Lay foundation */
        C    3    /* Rough plumbing */
        D   10    /* Frame */
        E    8    /* Finish exterior */
        F    4    /* Install HVAC */
        G    6    /* Rough electric */
        H    8    /* Sheet rock */
        I    5    /* Install cabinets */
        J    5    /* Paint */
        K    4    /* Final plumbing */
        L    2    /* Final electric */
        M    4    /* Install flooring */
;

set P[B] := A;
set P[C] := B;
set P[D] := B;
set P[E] := D;
set P[F] := D;
set P[G] := D;
set P[H] := C E F G;
set P[I] := H;
set P[J] := H;
set P[K] := I;
set P[L] := J;
set P[M] := K L;

end;