# Question about Pricing Problem in Column Generation

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?

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.