[Scip] Getting duals values of best solution

Sun Oct 19 02:56:13 CEST 2014

Dear Abdelkader,

1) In one of your previous mails you sent the code of your lp.cpp file. 
This is not how branch-and-price in SCIP works. You should not build the 
model, call SCIPsolve() and then try to generate new columns. In 
particular, since SCIP solves MIPs, what should be the dual value of a 
constraint after solving a MIP using branch-and-bound? If you want to do 
branch-and-price, you should implement a pricer plugin, like it is shown 
in the examples (Coloring and Binpacking), because this is called within 
the LP solving loop at every node ad generates new columns until no 
improving columns were found anymore and the LP solution is optimal for 
the (unrestricted) master problem. But I saw that you did this now in 
your current implementation.

2) In most cases, there is nothing such as "the optimal dual solution". 
Due to degeneracy, you often have more than one optimal (primal and/or 
dual) LP solutions. Which one your LP solver returns, is essentially 
random, so just that SCIP returns another dual solution does not mean 
that this one is wrong (as long as you have the same optimal value).

3) Your variable have upper bounds. These can be seen as additional 
constraints and have a dual multiplier themselves. Please check the 
reduced cost of your variables. They should be negative (which is ok, 
since they are at their upper bound, in this case they must be 
nonpositive in order to be optimal). But this also explains why you keep 
finding variables with negative reduced cost and keep generating 
columns. Please try to remove the upper bound from the columns or set a 
lazy upper bound of 1 for the columns (see 
http://scip.zib.de/doc/html/FAQ.php#whatarelazybounds).

Best,
Gerald

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20141019/fe45ae13/attachment.html>