[SCIP] [Scip] Question about column generation in scip

[Gerald Gamrath]

Dear Saleh,

it is ok to add some of the variables already during problem creation 
and then add others in pricing.

If you give the optimal solution as initial columns, this solution will 
be found directly in the beginning, but its optimality still has to be 
proven. And normally, there are other variables that help to improve the 
LP solution when priced. If this would not be the case, you would 
already be done without any branching. But often, you need some 
branching to prove optimality, which implies that your root dual bound 
is smaller (in case of minimization) than the optimum, so there are some 
variables not contained in the optimal solution which can improve the LP 
solution. In order to close the gap, you need to solve multiple node LPs 
and potentially generate variables there.

In branch-and-bound (without price), you see a similar thing: If you 
provide the optimal solution at the beginning of the solving process, 
this speeds up the process, but you still need a significant amount of 
branching for most of the instances.

Best,
Gerald

Am 21.09.2015 um 14:02 schrieb M. Farham:
> Hi all,
>
> Same question here.
> But I am not sure if I am giving the initial columns correctly. What I 
> do is to create a variable and add its coefficients to the objective 
> function and corresponding constraints before calling the pricer. Is 
> this ok, or should I price this variable and add it in the pricing stage?
>
> Bests,
>
> Saleh
>
> On Tue, Mar 10, 2015 at 12:36 AM, Abdelkader Ouali 
> <oualiaek at hotmail.fr <mailto:oualiaek at hotmail.fr>> wrote:
>
>     Hi all,
>
>     I have implemented branch-and-price using Scip,
>     and launch it to solve short examples before attacking big ones.
>     I noticed that when I give an optimal solution as initial columns
>     for the master or also during the solving, the pricing process
>     generates unused  columns, which are in final all zero (because
>     they not participate in optimal solution).
>     So, I wonder why the pricing generates columns while an already
>     optimal solution was given, is it due to duals given by Scip or ... ?
>
>     Thanks for any help
>     With regards
>     ---
>     A. Ouali
>
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto:Scip at zib.de>
>     http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
> -- 
> M Saleh F
>
>
> _______________________________________________
> 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/20150921/61375d13/attachment.html>