[Scip] Getting duals values of best solution
Abdelkader Ouali
oualiaek at hotmail.fr
Sun Oct 19 12:31:39 CEST 2014
Dear Gerald,
Thanks for reply, it was really helpful,I checked the documentation of lazy bounds,I understand the concept, but I don't have a clear idea on how it works inside scip,I used a lazy upper bound on variables of the example above SCIPchgVarUbLazy(scip, var, 1), and the dual values are correct.
I can go further now, thanks
A. Ouali
Date: Sun, 19 Oct 2014 02:56:13 +0200
From: gamrath at zib.de
To: oualiaek at hotmail.fr
CC: scip at zib.de
Subject: Re: [Scip] Getting duals values of best solution
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/2b3676ba/attachment.html>
More information about the Scip
mailing list