Question about Pricing Problem in Column Generation

Question

In column generation, we need to solve the following pricing problem : $$\min c_j-\bf{c}^T_B\bf{B}^{-1}\bf{N}_j$$ In the book, I saw authors say that according to duality theory, $\bf{y}^T = \bf{c}^T_B\bf{B}^{-1}$, where $\bf{y}$ is the dual solution, the above pricing problem is equivalent to $$\min c_j-\bf{y}^T\bf{N}_j$$

My question is: how to derive $\bf{y}^T = \bf{c}^T_B\bf{B}^{-1}$? Does this equation hold in every iteration of the Simplex iteration? Or it is true only at the optimal solution when Simplex finishes?

Answer 1

You don't really derive $y^\prime = c_B^\prime B^{-1}$, you just set $y$ to that expression. At every iteration but the last of the simplex method on the primal problem, $x_B = B^{-1}b$ and $x_N = 0$ gives a feasible but suboptimal solution to the primal problem and $y^\prime = c_B^\prime B^{-1}$ gives a superoptimal but infeasible solution to the dual problem. At the final step, the primal solution goes from suboptimal to optimal and the dual solution goes from infeasible to feasible.