Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Suppose you are solving a minimization problem with a column generation procedure, and that you have $2$ sub-problems. At some point, one of the $2$ sub-problems is no longer able to generate a column with negative reduced cost.
Does this sub-problem never have to be solved again ? Or is it possible that a few iterations later, given the interaction with new columns from the other sub-problem, it is possible that a new column may be found ?
Thanks !
You can only stop when all subproblems fail to find a negative reduced cost column. So, no, when one subproblem does not find a column in one iteration you cannot conclude that you need not call it again.
Below you see an instance with 40+ subproblems (one for each color). Over the iterations, in fact most subproblems are unsuccessful, but later still find columns. This plot shows the initial Farkas pricing (when the RMP is still infeasible), the root node, and the remainder of the tree.
