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

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150927/bc7f71b1/attachment.html>