[SCIP] About dual solution in a column generation approach

[Ambros Gleixner]

Dear Diego,

I am a bit suspicious about the initial dual solution with value -10. 
The log shows that SCIP finds a -24 primal solution as solution of the 
initial LP solve (symbol "*" on the left).  This looks like SoPlex 
returns a dual solution with value -24.

When you calculate your dual solution, do you take into account that 
there may be nonzero dual multipliers for the upper bounds of your 
variables?  If not, you can avoid this by declaring them to be lazy, see FAQ

    http://scip.zib.de/doc-5.0.1/html/FAQ.php#whatarelazybounds

and the use of SCIPchgVarUbLazy() in 
examples/Binpacking/src/pricer_binpacking.c.

Best,
Ambros


Am 25.04.2018 um 14:05 schrieb dponce at us.es:
> Dear Ambros,
> 
> I thought exactly the same. It would be a natural explanation for the 
> behavior. But you can see in the attached output the same oscilation, 
> setting the flag removable to FALSE in the function SCIPcreateVar().
> 
> Best.
> 
> Diego.
> 
> 
> El 25/04/2018 10:41, Ambros Gleixner escribió:
> 
>> 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 <mailto: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