[Scip] Getting duals values of best solution
Ambros Gleixner
gleixner at zib.de
Sun Oct 19 01:48:52 CEST 2014
Dear Abdelkader,
I just noticed I misunderstood your e-mail. You were not complaining
that the reduced cost values are zero, but the dual multipliers for the
constraints.
I cannot see an obvious flaw in your program. Are you running it in
debug mode? I.e. have you compiled SCIP with make OPT=dbg (under
Linux). You should do this. Also, run a memory checker like valgrind
if available.
Another check you could make before calling SCIPgetDualsolLinear() is
whether SCIPgetRowLinear() does *not* return NULL.
Hope that helps,
Ambros
Am 19.10.2014 um 01:26 schrieb Ambros Gleixner:
> Dear Abdelkader,
>
> if the duals are
>
> > Duals : -2 -1 0 0
>
> then the reduced costs for your problem are indeed zero:
>
> obj - y^T A
> = (-1,-2,0,0) - (-2) * (0,1,0,0) - (-1) * (1,0,0,0)
> = (0,0,0,0)
>
> so everything looks fine.
>
> Ambros
>
>
>
> Am 18.10.2014 um 14:56 schrieb Abdelkader Ouali:
>> Dear Thomas,
>>
>> I checked again my code, and still not figure out where the problem is,
>> to be more clear, during the column generation, Scip found the optimal
>> solution of the restricted master problem, which is optimal for the
>> master problem, when I look for dual values to compute the reduced cost
>> they are all zero, and I get negative reduced cost allowing SCIP to
>> generate more variables.
>> I took these short examples as ILP, which is one step "when it founds
>> optimal solution" during column generation, I have attached in this mail
>> the source code of this ILP and the pricer.
>>
>> /Minimize/
>> / Obj: -1 x0 -2 x1/
>> /Subject to/
>> / c0: +1 x1 = +1/
>> / c1: +1 x0 = +1/
>> / c2: +1 x0 = +1/
>> / c3: +1 x0 +1 x1 = +2/
>> /Bounds/
>> / 0 <= x0 <= 1/
>> / 0 <= x1 <= 1/
>> /Binaries/
>> / x0 x1/
>> /End/
>>
>> I checked the dual values using cplex by providing this example, and it
>> gives the following duals
>> obj: -3
>> x0 = 1
>> x1 = 1
>> Duals : -2 -1 0 0
>>
>> but when i get the dual values during the pricing process, i found this
>> as a result
>>
>> obj: -3
>> x0: 1
>> x1: 1
>> _____________________________________________________
>> DUAL values :
>> Pi[i]= -0, -0, -0, -0,
>> _____________________________________________________
>>
>> I check if i used transformed constraint by using
>> SCIPconsIsTransformed(), and it returns true.
>> So, why i'm not getting the correct values of dual variables ?
>>
>> Sorry for the long mail, and thanks for any explanations
>>
>> A. Ouali
>>
>>
>> > Date: Fri, 17 Oct 2014 08:33:31 +0200
>> > Subject: Re: [Scip] Getting duals values of best solution
>> > From: schlechte at zib.de
>> > To: oualiaek at hotmail.fr
>> > CC: rodolfo.carvajal at gmail.com; scip at zib.de
>> >
>> > Dear Abdelkader,
>> >
>> > have a look at
>> >
>> > http://scip.zib.de/doc/examples/Binpacking/
>> >
>> > and in particular
>> >
>> >
>> http://scip.zib.de/doc/examples/Binpacking/pricer__binpacking_8c_source.shtml
>>
>> >
>> > Good luck.
>> > Thomas
>> >
>> >
>> > > Hi Rodolfo,
>> > > Thank's for reply.
>> > > But when applying pricing, we use dual values to get the reduced
>> cost,in
>> > > my case, i don't get the correct values of dual variables.The
>> earlier
>> > > example is one iteration of column generation, at these stepscip
>> found the
>> > > optimal solution of the master problem, so no need to generate new
>> > > columns,the problem is that the value of dual variable are all
>> zero, which
>> > > is not correct, and scipcontinue to generate new columns.
>> > > So how we can get dual variables in pricing if scip don't provide
>> dual
>> > > information ?
>> > > Best regards
>> > > A. Ouali
>> > >
>> > >
>> > > Date: Thu, 16 Oct 2014 18:17:20 -0300
>> > > Subject: Re: [Scip] Getting duals values of best solution
>> > > From: rodolfo.carvajal at gmail.com
>> > > To: oualiaek at hotmail.fr
>> > >
>> > > Hi Abdelkader,
>> > >
>> > > If you solve your MIP as a SCIP problem, you don't get dual
>> information
>> > > (see the SCIP FAQ http://scip.zib.de/#faq).
>> > >
>> > > You can use the LP interface (lpi/lpi.h) to interact with the LP
>> solver
>> > > and get the duals.
>> > > Hope this helps,
>> > >
>> > > Rodolfo
>> > > On Oct 16, 2014 5:49 PM, "Abdelkader Ouali" <oualiaek at hotmail.fr>
>> wrote:
>> > >
>> > >
>> > >
>> > > Dear scip users,
>> > > I have a short example of ILP, and i want to know how to get dual
>> values
>> > > of optimal solution,when i use cplex, it give me the correct value
>> of dual
>> > > variables,but when using scip the dual values is all zero, knowing
>> that i
>> > > set the pointers of constraint to the transformedones, in
>> attachment you
>> > > will find source code containing the example and how i do to get
>> the dual
>> > > values.
>> > > I want to know what is wrong in this code ?
>> > > Best regards
>> > > A. Ouali
>> > >
>> > > _______________________________________________
>> > >
>> > > Scip mailing list
>> > >
>> > > Scip at zib.de
>> > >
>> > > http://listserv.zib.de/mailman/listinfo/scip
>> > >
>> > >
>> > > _______________________________________________
>> > > Scip mailing list
>> > > Scip at zib.de
>> > > http://listserv.zib.de/mailman/listinfo/scip
>> > >
>> >
>> >
>> >
>> > _____________________________________________
>> >
>> > Dr. Thomas Schlechte
>> > Zuse Institute Berlin
>> > Takustrasse 7, D-14195 Berlin-Dahlem, Germany
>> > phone: +49-30 841 85 317
>> > fax: +49-30 841 85 269
>> > url: http://www.zib.de/schlechte
>> > e-mail: schlechte at zib.de
>> > _____________________________________________
>> >
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>
--
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner
More information about the Scip
mailing list