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?
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.