11
$\begingroup$

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 !

$\endgroup$
15
$\begingroup$

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. enter image description here

| improve this answer | |
$\endgroup$

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.