# LP column Generation - Why are we adding the variable with smallest reduced cost?

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?

• Your question has more to do with the simplex method in general than with column generation. – LinAlg Mar 26 '18 at 19:52
• 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. – Erwin Kalvelagen Mar 27 '18 at 4:52
• @LinAlg good point! I’ve added in the simplex tag. Thanks. – hklel Mar 27 '18 at 4:53
• @ErwinKalvelagen but is there any advantage of adding the smallest one that can be mathematically proven? – hklel Mar 27 '18 at 4:55
• 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).. – Erwin Kalvelagen Mar 27 '18 at 6:20