Thursday, 14:15 - 14:40 h, Room: H 2032


Jacques Desrosiers
Row-reduced column generation for highly degenerate master problems

Coauthors: Jean Bertrand Gauthier, Marco E. L├╝bbecke


Column generation alternately solves a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy, exposing what is known as tailing-off effect. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation that takes advantage of degenerate solutions. The idea is to reduce the number of constraints to the current number of positive basic variables. The advantage of this row-reduction is a smaller basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem that needs to generate variables compatible with the row-reduction, if possible. Otherwise, incompatible variables may need to be added, and the row-reduction is dynamically updated. We show that, in either case, a strict improvement in the objective function value occurs.


Talk 3 of the invited session Thu.2.H 2032
"Branch-and-price III: New techniques" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  payday loan . Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.