Reduced cost in column generation

Question

I am following this tutorial to learn column generation. ` https://co-at-work.zib.de/slides/Donnerstag_24.9/cgbpdw-coatwork-annotated.pdf

I have a couple of questions I thought someone experienced in this topic could help me understand.

1. How are the initial columns selected for the restricted master problem (RMP)?

2. After solving the restricted master problem and obtaining dual variables, do we compute the reduced cost of the other variables that were not included in the RMP or all variables? This applies to pricing problems too. Does the pricing problem include all variables or only the variables that were not included in the RMP?

Here are the slides that describes column generation and pricing problem:

Answer 1

You typically give the initial RMP enough columns to make it feasible. A common approach is to apply some heuristic or metaheuristic to the underlying problem and use the columns corresponding to the solution it provides (assuming the heuristic succeeds in finding at least one solution). In some cases, there may be a problem-specific "obvious" feasible solution, so you can start with the columns employed by that solution.

If you know all of $J$ (highly unlikely in practice), in the pricing problem you evaluate $\bar{c}_j$ for $j\in J\backslash J'.$ You already know $\bar{c}_j$ for $j\in J'$ (and know that they are nonnegative) because those are the reduced costs in the final simplex tableau from solving the RMP. In practice, the pricing subproblem is typically some sort of LP, whose objective function is computed using $\pi$ and whose solution and objective value are respectively a new column (in $J$ but not $J'$) and the reduced cost of the corresponding variable $\lambda_j$ that you will introduce in the master problem.