[Scip] farkas pricing
Alessia Violin
aviolin at ulb.ac.be
Fri May 17 12:17:58 MEST 2013
Hello Martin,
thanks for you answer.
I am not using SCIPisLT but I compare the redcost with an epsilon, which
should be the same (indeed at the beginning I had numerical problems as
I was not doing it). Moreover my redcost from the farkas pricing that
gets into the infinite loop is of the order of 10, so I shouldn't have
numerical troubles.
For the implementation I am using a flag for "isfarkas", so I didn't
copy the whole code but I just have a couple of if to choose the correct
dual to extract and objective function, depending on it.
About the rest I did my best to check the code, but I will continue as
obviously there is a problem somewhere, I just wanted to check that I
was not missing something...
Best,
Alessia
On 05/16/2013 07:52 PM, Martin Bergner wrote:
> Hi Alessia,
>
>> For other instances it may happen that after branching the current
>> master is not feasible any more so I need to use Farkas pricing to
>> restore feasibility right?
> Yep, that's how I would do that, too.
>
>> Here I have troubles, since the farkas
>> pricing gets into an infinite loop keeping finding and adding the same
>> column. Do you have an idea of why this is happening?
> My usual suspect here is that you compare redcost < 0 and not with
> SCIPisLT(scip, redcost, 0) but since your redcost pricing seems to work,
> I guess you implemented that correctly.
>
>> My farkas pricing is the same as the redcost pricing, but with zero
>> objective function and instead of taking normal dual variables I take
>> the farkas ones with the function SCIPgetDualfarkasLinear.
> That sounds perfect.
>
>> My master problem is a maximization one, but I know that scip transforms
>> everything into a min problem, so I considered this in the redcost
>> pricing and in the farkas pricing as well, do they work the same at this
>> regard?
> Indeed, they should be completely identical up to the extraction of the
> dual solution and the objective function, as you wrote.
>
> Have you copied the code and just replaced every objective with 0 and
> every SCIPgetDualsol with SCIPgetDualfarkas or have you chosen an
> implementation with a boolen flag as suggested in the most recent
> documentation? Are you sure you haven't forgotten anything buried deep
> in the code?
>
> Regards,
> Martin
>
>
>
>
--
Alessia Violin
Service Graphes et Optimisation Mathématique (G.O.M.)
Université Libre de Bruxelles
C.P. 210/01
Boulevard du Triomphe
B-1050 BRUXELLES
Tel: 02 650 58 80 - Fax: 02 650 59 70
Email: aviolin at ulb.ac.be
Webpage: http://homepages.ulb.ac.be/~aviolin/
More information about the Scip
mailing list