Project scheduling duality

On the augmented precedence graph, the linear programming problemhas dual $\max {\sum }_{i\to j}{\tau }_i{f}_{ij}$, with $f\ge 0$ a unit source-to-sink flow. Equivalently, the dual is the negative of the optimal uncapacitated minimum-cost flow value with arc costs $-{\tau }_i$. The flow selects a longest path, while the time variables provide a matching weak duality bound.

// Target: mathematical-optimization.bigb

A feasible timetable with finish time $T$ and a unit flow carried on a precedence path of total duration $T$ certify optimality. Summing the inequalities $t_j-t_i\ge {\tau }_i$ along that path proves every schedule needs at least $T$, while the timetable attains it.

// Target: computer-science.bigb