[SCIP] About dual solution in a column generation approach

[Ambros Gleixner]

Dear Diego,

Sorry that we have been slow in answering.  It seems like a tricky question.


Am 17.04.2018 um 17:20 schrieb dponce at us.es:
> Dear SCIP,
> 
> Developing a B&P project, we have some questions about the behavior we 
> have among the different iterations of the pricer.
> 
> Attached you have the output of a set partitioning formulation for which 
> eventually the optimal solution is reached. But still I see a couple of 
> things I don't understand:
> 
>   * Line 109. Why the first solution of the dual problem is not -24.0?
>     With the initial variables the dual problem should have constraints
>     to avoid solution -10.0.
>   * Line 279. If previously the solution was -114.0, why suddenly goes
>     back to -112.0?

It seems that many LP columns have been removed from the LP, since the 
value in the output column labeled "cols" drops from 62 to 29.  I am not 
an expert user of branch-and-price in SCIP, does somebody have a 
suggestion how to analyze/avoid the behavior?


> Regarding this previous question
> 
> http://listserv.zib.de/pipermail/scip/2017-July/003156.html
> 
> and the binpacking example, we have disabled the preprocessing.

During pricing you can always query the dual solution for the 
transformed problem, so there is no need to disable presolving.  This is 
only necessary if you want to obtain the dual solution for an LP that 
you solve with SCIP "out of the box".


> Is it 
> disabled in the VRP example?

I don't think so.

Best,
Ambros



> Dual solution has been handily calculated from the dual multiplier. Are 
> there some SCIP function to make this for the current solution? And for 
> primal? Anyway, we trust on our calculation and this is a way to check 
> the correctness of the dual multiplier values.
> 
> We are debugging our code, but right now, we don't have more ideas. We 
> have thought in DELAY and removable option in the variables as an 
> explanation of this behavior, but nothing.
> 
> Thanks in advance for the help.
> 
> Best.
> 
> Diego Ponce.
> 
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
Ambros Gleixner, Research Group Mathematical Optimization Methods at 
Zuse Institute Berlin, http://www.zib.de/gleixner