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

[M. Farham]

Thank you Gerald.

What I did was to give the initial column to the pricer, price it, and then
add it to the MP in the very beginning. The rest is done as before. The
problem is solved by this additional step.

Best,
Saleh

On Sat, Oct 3, 2015 at 9:37 PM, Gerald Gamrath <gamrath at zib.de> wrote:

> 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> 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>
>> 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
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>
>>
>> --
>> M Saleh F
>>
>>
>> _______________________________________________
>> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>
>
> --
> M Saleh F
>
>
> _______________________________________________
> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>
>
>


-- 
M Saleh F
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20151007/7e194c58/attachment.html>