<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi Mahdi,<br>
<br>
I can second Marco's guess, your pricing problem probably works
incorrectly.<br>
<br>
SCIP gets the value for the dual bound by solving the master LP to
optimality. In a branch-and-price context, this means that the
restricted master is solved to optimality, new variables are
created based on the dual values, the restricted master is solved
again, etc. When at some point, the pricer does not generate any
new variable, SCIP assumes that this means that there is no
improving variable and takes the LP value as a dual bound. If you
want to stop generating variables early in order to reduce the
tailing-off effect, you need to set the result pointer of the
pricer to SCIP_DIDNOTRUN instead of SCIP_SUCCESS. This tells SCIP
that there might still be improving variables and the LP value is
no valid dual bound. See also
<a class="moz-txt-link-freetext" href="http://scip.zib.de/doc/html/PRICER.shtml">http://scip.zib.de/doc/html/PRICER.shtml</a><br>
<br>
Do you have a minimization or maximization problem? In the latter
case, perhaps you forgot to multiply the original objective
coeffcients of the variables by -1 when creating the variable, see<br>
<a class="moz-txt-link-freetext" href="http://scip.zib.de/doc/html/scip_8h.shtml#aadcc57e6efe08c07a23643d0e7fb3151">http://scip.zib.de/doc/html/scip_8h.shtml#aadcc57e6efe08c07a23643d0e7fb3151</a><br>
<br>
Best,<br>
Gerald<br>
<br>
On 06.08.2013 14:09, Marco Lübbecke wrote:<br>
</div>
<blockquote
cite="mid:CAM5ELAqMAdWkGy7gy1+pN-G8sTNekkS6r9Z1fpftX2X-1RNSSA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>First short: you do not generate "all" columns, that is,
your pricing problem is buggy. Check whether you calculate
reduced costs correctly, check whether your pricing problem
formulation is correct, verify with toy examples that you can
(and do) solve by hand for comparison.<br>
<br>
</div>
Bests,<br>
Marco<br>
<br>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">2013/8/6 Mahdi Noorizadegan (DIMAP) <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:phd09mn@mail.wbs.ac.uk" target="_blank">phd09mn@mail.wbs.ac.uk</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">
<div>
<div>
<div>
<div>
<div>Dear SCIP,<br>
<br>
</div>
I am trying to solve a variant of VRP in SCIP
within branch and price algorithms.<br>
</div>
The problem is that after few iterations without any
dual bound and infinite gap, it generates a lower
bound which is higher than the optimal solution of
the instance I solve. <br>
</div>
I was wondering if you could help me to understand how
SCIP generates the dual bound and why while it is
still in early stages it generates very high lower
bound?<br>
<br>
</div>
Thanks<span class="HOEnZb"><font color="#888888"><br>
</font></span></div>
<span class="HOEnZb"><font color="#888888">Mahdi<br>
</font></span></div>
<br>
_______________________________________________<br>
Scip mailing list<br>
<a moz-do-not-send="true" href="mailto:Scip@zib.de">Scip@zib.de</a><br>
<a moz-do-not-send="true"
href="http://listserv.zib.de/mailman/listinfo/scip"
target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<br>
-- <br>
Prof. Dr. Marco Lübbecke<br>
RWTH Aachen University <br>
Chair of Operations Research <br>
Kackertstrasse 7 <br>
D-52072 Aachen <br>
Germany <br>
<br>
fon / fax: +49 241 80-93362 / 92369 <br>
<a moz-do-not-send="true"
href="mailto:marco.luebbecke@rwth-aachen.de" target="_blank">marco.luebbecke@rwth-aachen.de</a><br>
<a moz-do-not-send="true"
href="http://www.or.rwth-aachen.de/luebbecke" target="_blank">www.or.rwth-aachen.de/luebbecke</a>
</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>