[Scip] Getting duals values of best solution

[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