§2, pp. 94–95 — the solution rebuilt from the y*_ij has objective value LB

Assume the setting of the principal result: $m\ge2$, $b_i>0$, $r_{ij}\ge0$, a cheapest-agent selection $j\mapsto i_j$, and optimal solutions $y^*_i$ of (PK$_i$) for $i\in I'$. For every task $j$ let $k_j\ne i_j$ be an agent with $p_j=c_{k_jj}-c_{i_jj}$. Build $x'$ from the (PR) solution: every task $j$ with $i_j\in I'$ and $y^*_{i_jj}=1$ is taken from $i_j$ ($x'_{i_jj}=0$) and given to $k_j$ ($x'_{k_jj}=1$); every other task stays with $i_j$. Then $x'$ is feasible for (PR) and

Consequently, if $x'$ also satisfies the resource constraints, i.e. is feasible for (P), it is an optimal solution of (P).

The construction is how the algorithm finds candidate incumbents: the knapsack solutions say which tasks to move, and the move costs exactly the penalty.

Formalization Note The optimality conclusion combines the cost identity with the principal result, so it carries the same hypotheses ($r_{ij}\ge0$, $b_i>0$, $m\ge2$). Agents and tasks are 0-based.