/* 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;