I found this lecture note on column generation, which is a well-known algorithm for solving LP instances with a large number of columns.

On page 9, it says that at each iteration, we need to find the variable with smallest reduced cost and add it as a new basic variable.

My question is, why should we add the smallest (most negative) reduced cost variable? As far as I know, adding any variable with negative reduced cost helps the problem, so why should we explicitly choose the smallest one? Is there any advantage of doing this that can be mathematically proven?

  • $\begingroup$ Your question has more to do with the simplex method in general than with column generation. $\endgroup$ – LinAlg Mar 26 '18 at 19:52
  • $\begingroup$ You can pick any candidate column with negative reduced cost. Intuitively it makes sense to pick the most negative one. This is analog to choosing the entering variable in the Simplex method. $\endgroup$ – Erwin Kalvelagen Mar 27 '18 at 4:52
  • $\begingroup$ @LinAlg good point! I’ve added in the simplex tag. Thanks. $\endgroup$ – hklel Mar 27 '18 at 4:53
  • $\begingroup$ @ErwinKalvelagen but is there any advantage of adding the smallest one that can be mathematically proven? $\endgroup$ – hklel Mar 27 '18 at 4:55
  • 1
    $\begingroup$ The reduced cost is like a gradient. Make sense to pick the one that improves the objective the most when taking a small step.However it is a heuristic: there may be other columns that are in the end more profitable. See any LP book (they will invariable discuss reduced costs and the Dantzig pricing rule).. $\endgroup$ – Erwin Kalvelagen Mar 27 '18 at 6:20

You are correct: you do not have to choose the variable with smallest reduced cost. In fact, in state of the art customized solvers that use column generation, heuristics are often used to solve the subproblem to find any column with negative reduced cost.

  • $\begingroup$ I did some experiments with my own problem, and I found that adding variables with smaller reduced cost did solve the problem in fewer iterations than adding those with larger cost, but I can’t find a way to prove this. $\endgroup$ – hklel Mar 26 '18 at 15:01
  • $\begingroup$ Btw, what are those customised solvers you mentioned? Any link to paper or solver name? Thanks a lot! $\endgroup$ – hklel Mar 26 '18 at 15:02
  • 1
    $\begingroup$ To my knowledge, this is not true in the general case. Most customised solvers are tailor made (its a lot of work), but you can use Dippy (pypi.python.org/pypi/coinor.dippy). $\endgroup$ – Kuifje Mar 26 '18 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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