<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Dear Abdelkader,<br>
<br>
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.<br>
<br>
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).<br>
<br>
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
<a class="moz-txt-link-freetext" href="http://scip.zib.de/doc/html/FAQ.php#whatarelazybounds">http://scip.zib.de/doc/html/FAQ.php#whatarelazybounds</a>).<br>
<br>
Best,<br>
Gerald<br>
<br>
<br>
<div class="moz-cite-prefix">Am 18.10.2014 um 14:56 schrieb
Abdelkader Ouali:<br>
</div>
<blockquote cite="mid:DUB115-W442FF0CC72C86B3D31408DABA90@phx.gbl"
type="cite">
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style>
<div dir="ltr"><font style="font-size:12pt;"
face="Calibri,sans-serif" size="3" color="#000000">Dear
Thomas,</font>
<div><font style="font-size:12pt;" face="Calibri,sans-serif"
size="3" color="#000000"><br>
</font></div>
<div>
<div>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.</div>
<div>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.</div>
</div>
<div><font face="Calibri,sans-serif" color="#000000">
<div><br>
</div>
<div><i>Minimize</i></div>
<div><i> Obj: -1 x0 -2 x1</i></div>
<div><i>Subject to</i></div>
<div><i> c0: +1 x1 = +1</i></div>
<div><i> c1: +1 x0 = +1</i></div>
<div><i> c2: +1 x0 = +1</i></div>
<div><i> c3: +1 x0 +1 x1 = +2</i></div>
<div><i>Bounds</i></div>
<div><i> 0 <= x0 <= 1</i></div>
<div><i> 0 <= x1 <= 1</i></div>
<div><i>Binaries</i></div>
<div><i> x0 x1</i></div>
<div><i>End</i></div>
<div><br>
</div>
<div>I checked the dual values using cplex by providing this
example, and it gives the following duals </div>
<div>obj: -3</div>
<div> x0 = 1</div>
<div> x1 = 1</div>
<div>Duals : -2 -1 0 0</div>
<div><br>
</div>
<div>but when i get the dual values during the pricing
process, i found this as a result </div>
<div><br>
</div>
<div>
<div>obj: -3</div>
<div>x0: 1</div>
<div>x1: 1</div>
<div>_____________________________________________________</div>
<div>DUAL values : </div>
<div>Pi[i]= -0, -0, -0, -0, </div>
<div>_____________________________________________________</div>
</div>
<div><br>
</div>
<div>I check if i used transformed constraint by using
SCIPconsIsTransformed(), and it returns true.</div>
<div>So, why i'm not getting the correct values of dual
variables ?</div>
<div><br>
</div>
<div>Sorry for the long mail, and thanks for any
explanations </div>
<div><br>
</div>
<div>A. Ouali </div>
<div> </div>
</font></div>
<div><br>
<br>
<div>> Date: Fri, 17 Oct 2014 08:33:31 +0200<br>
> Subject: Re: [Scip] Getting duals values of best
solution<br>
> From: <a class="moz-txt-link-abbreviated" href="mailto:schlechte@zib.de">schlechte@zib.de</a><br>
> To: <a class="moz-txt-link-abbreviated" href="mailto:oualiaek@hotmail.fr">oualiaek@hotmail.fr</a><br>
> CC: <a class="moz-txt-link-abbreviated" href="mailto:rodolfo.carvajal@gmail.com">rodolfo.carvajal@gmail.com</a>; <a class="moz-txt-link-abbreviated" href="mailto:scip@zib.de">scip@zib.de</a><br>
> <br>
> Dear Abdelkader,<br>
> <br>
> have a look at<br>
> <br>
> <a class="moz-txt-link-freetext" href="http://scip.zib.de/doc/examples/Binpacking/">http://scip.zib.de/doc/examples/Binpacking/</a><br>
> <br>
> and in particular<br>
> <br>
>
<a class="moz-txt-link-freetext" href="http://scip.zib.de/doc/examples/Binpacking/pricer__binpacking_8c_source.shtml">http://scip.zib.de/doc/examples/Binpacking/pricer__binpacking_8c_source.shtml</a><br>
> <br>
> Good luck.<br>
> Thomas<br>
> <br>
> <br>
> > Hi Rodolfo,<br>
> > Thank's for reply.<br>
> > But when applying pricing, we use dual values to
get the reduced cost,in<br>
> > my case, i don't get the correct values of dual
variables.The earlier<br>
> > example is one iteration of column generation, at
these stepscip found the<br>
> > optimal solution of the master problem, so no need
to generate new<br>
> > columns,the problem is that the value of dual
variable are all zero, which<br>
> > is not correct, and scipcontinue to generate new
columns.<br>
> > So how we can get dual variables in pricing if
scip don't provide dual<br>
> > information ?<br>
> > Best regards<br>
> > A. Ouali<br>
> ><br>
> ><br>
> > Date: Thu, 16 Oct 2014 18:17:20 -0300<br>
> > Subject: Re: [Scip] Getting duals values of best
solution<br>
> > From: <a class="moz-txt-link-abbreviated" href="mailto:rodolfo.carvajal@gmail.com">rodolfo.carvajal@gmail.com</a><br>
> > To: <a class="moz-txt-link-abbreviated" href="mailto:oualiaek@hotmail.fr">oualiaek@hotmail.fr</a><br>
> ><br>
> > Hi Abdelkader,<br>
> ><br>
> > If you solve your MIP as a SCIP problem, you don't
get dual information<br>
> > (see the SCIP FAQ <a class="moz-txt-link-freetext" href="http://scip.zib.de/#faq">http://scip.zib.de/#faq</a>).<br>
> ><br>
> > You can use the LP interface (lpi/lpi.h) to
interact with the LP solver<br>
> > and get the duals.<br>
> > Hope this helps,<br>
> ><br>
> > Rodolfo<br>
> > On Oct 16, 2014 5:49 PM, "Abdelkader Ouali"
<a class="moz-txt-link-rfc2396E" href="mailto:oualiaek@hotmail.fr"><oualiaek@hotmail.fr></a> wrote:<br>
> ><br>
> ><br>
> ><br>
> > Dear scip users,<br>
> > I have a short example of ILP, and i want to know
how to get dual values<br>
> > of optimal solution,when i use cplex, it give me
the correct value of dual<br>
> > variables,but when using scip the dual values is
all zero, knowing that i<br>
> > set the pointers of constraint to the
transformedones, in attachment you<br>
> > will find source code containing the example and
how i do to get the dual<br>
> > values.<br>
> > I want to know what is wrong in this code ?<br>
> > Best regards<br>
> > A. Ouali<br>
> ><br>
> > _______________________________________________<br>
> ><br>
> > Scip mailing list<br>
> ><br>
> > <a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a><br>
> ><br>
> > <a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a><br>
> ><br>
> ><br>
> > _______________________________________________<br>
> > Scip mailing list<br>
> > <a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a><br>
> > <a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a><br>
> ><br>
> <br>
> <br>
> <br>
> _____________________________________________<br>
> <br>
> Dr. Thomas Schlechte<br>
> Zuse Institute Berlin<br>
> Takustrasse 7, D-14195 Berlin-Dahlem, Germany<br>
> phone: +49-30 841 85 317<br>
> fax: +49-30 841 85 269<br>
> url: <a class="moz-txt-link-freetext" href="http://www.zib.de/schlechte">http://www.zib.de/schlechte</a><br>
> e-mail: <a class="moz-txt-link-abbreviated" href="mailto:schlechte@zib.de">schlechte@zib.de</a><br>
> _____________________________________________<br>
> <br>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</body>
</html>