5
$\begingroup$

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:

![enter image description here

enter image description here enter image description here

enter image description here

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Another common and more generic approach for the initial columns is to add a dummy column with high cost for each unsatisfied constraint $\endgroup$
    – fontanf
    Oct 21, 2022 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.