= Project scheduling duality
On the augmented precedence graph, the <linear programming> problem
$$
\min(t_{\mathrm{sink}}-t_{\mathrm{source}})
\quad\text{subject to}\quad t_j-t_i\geq\tau_i
$$
has dual $\max\sum_{i\to j}\tau_i f_{ij}$, with $f\geq0$ 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
Back to article page
