[SCIP] Question about Column Generation !

Gerald Gamrath gamrath at zib.de
Sat Dec 5 23:38:25 CET 2015

Dear Abdelkader,

in column generation, we are looking for improving variables, i.e. 
variables with negative reduced cost (for minimization problems) which 
the Simplex algorithm would enter into the basis. However, in the 
pricing routine of column generation, we are only adding those variables 
to the problem and are not adding them to the basis. After those 
variables were added, the RMP will be re-optimized, and in this course, 
the Simplex algorithm (if used) will decide on a column to enter the 
basis and one to leave it (in each iteration, it might need multiple 
ones to reach optimality again).


Am 05.12.2015 um 22:07 schrieb Abdelkader Ouali:
> Hi scip community,
> As column generation is based on simplex algorithm,
> I want to know, why we need "only" to enter a column into the 
> restricted master problem (RMP), and not to select a column as an 
> outgoing column after each solving of the RMP relaxation?
> Thanks for any answer.
> Kind regards
> ---
> A. Ouali
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20151205/ba8ed758/attachment.html>

More information about the Scip mailing list