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

[Gerald Gamrath]

Dear Saleh,

this sounds like you have a bug in your pricer and sometimes miss to 
generate needed variables. Given that adding initial columns will lead 
to different LP optima with potentially different dual multipliers, it 
may just be luck that sometimes, you end up with the optimal solution 
and sometimes not.

Sorry for not having a constructive answer to your question...

Best,
Gerald

Am 27.09.2015 um 14:48 schrieb M. Farham:
> Dear Gerald,
>
> Thank you for your kind response.
> However, I got another problem. I am dealing with the VRP and I am 
> trying to add an initial column before solving the problem. In some 
> cases, the solver fails to find the optimal solution when the initial 
> column is added to the MP. I also noticed that sometimes, the dual 
> bound is higher than the primal bound at the final node for this 
> minimization problem.
>
> Marking the initial variable as deletable and setting 
> 'lp/cleanupcolsroot' and 'pricing/delvarsroot' parameters to TRUE did 
> not help. But, if I reduce the 'lp/colagelimit' value, the problem is 
> solved to optimality and no bound conflicts are observed (I have to 
> set that parameter to 0 for some instances to get the correct solution).
>
> I have already checked the initial column for feasibility and I wonder 
> why this happens.
>
> Bests,
> Saleh
>
>
> On Tue, Sep 22, 2015 at 12:52 AM, Gerald Gamrath <gamrath at zib.de 
> <mailto:gamrath at zib.de>> wrote:
>
>     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  <mailto:Scip at zib.de>
>>     http://listserv.zib.de/mailman/listinfo/scip
>
>
>     _______________________________________________
>     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/20151003/906ad770/attachment.html>