<html>
<head>
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Hi Jungeun,</p>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Malgun Gothic";
panose-1:2 11 5 3 2 0 0 2 0 4;}
@font-face
{font-family:"Malgun Gothic";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:85.05pt 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have been using SCIP framework with its
own solver(Soflex) to implement Branch and Price, which
requires dual solutions of the restricted master problem to
calculate the reduced costs of additional columns.<o:p></o:p></p>
<p class="MsoNormal">After running a few sample instances, I
started doubt the accuracy of the dual solutions because
Pricer keeps generating columns at the root node with the
negative reduced costs but the lower bound of the node didn’t
reduce. ( Sometimes it even increased very little bit
(1e-10), but I guess its because of the optimality tolerance
setting)</p>
</div>
</blockquote>
<p>This is not how it works. If the lower bound could reduce, it
wouldn't be a lower bound. :-) If the LP value can still reduce
because pricers may find improving solutions, SCIP won't use this
as the lower bound for the node. Therefore, you should not see a
change in the lower bound unless the pricers are done and cannot
add any improving solutions (or you compute a valid lower bound
yourself and pass it to the lowerbound pointer). You could set
"display/lpobj/active = 2" to get a display column that show the
actual LP value, or access it via SCIPgetLPObjval. This should
hopefully go up.</p>
<p>On the other hand, there is degeneracy in many LPs, so it may
happen that you do some degenerate pivots and the LP value does
not increase after you added a column.<br>
</p>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<div class="WordSection1">
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I looked up this SCIP archive and found the
related one: <a
href="http://listserv.zib.de/pipermail/scip/2019-November/003806.html"
target="_blank" moz-do-not-send="true"><span
style="font-size:11.5pt;font-family:"Arial",sans-serif;background:#F8F8F8">http://listserv.zib.de/pipermail/scip/2019-November/003806.html</span></a><o:p></o:p></p>
<p class="MsoNormal">According to the answer, I set
presolving/maxrestarts = 0 , propagating/maxrounds=0 and
propagating/maxroundsroot=0 , but still the dual solution
seems not accurate.</p>
</div>
</blockquote>
This question is about something different, namely, how to call SCIP
on your LP problem and get dual values. However, this is not
recommended. If you really only want to solve an LP, then you should
use an LP solver, like So*P*lex, not SCIP, which is a MIP solver.
Within SCIP, however, many LPs are solved internally, for the
presolved problem at the current nodes, by the linked LP solver, and
this is where you get your dual solution from in case of
branch-and-price. But those LPs are already solved with SoPlex or
CPLEX, not with SCIP.<br>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<div class="WordSection1">
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have tested the dual solutions in
multiple ways. For example, I let SCIP and CPLEX solver read
the same .lp file and obtained the dual solutions using each
lp solver, respectively. Then, solved the same subproblem
using two different sets of dual solutions. With the dual
solutions of SCIP(Soflex), the subproblem found a column with
the negative reduced costs whereas the subproblem objective
value using dual solutions of Cplex was positive.
</p>
</div>
</blockquote>
<p>As I said, SCIP is not an LP solver, and its presolving methods
are not built to support returning dual solutions for your
original problem. You might want to use SoPlex for this.
Otherwise, you probably need to follow the advide given in the
link above, but you should also disable presolving completely, as
mentioned there as well.</p>
<p>Additionally: what do you mean with negative reduced costs, I
hope you use a tolerance? Also, it sounds suspicious that the dual
solution of CPLEX results in a positive objective value for the
subproblem. This should normally not happen, because there should
be variables with reduced cost 0, e.g., the current basic
variables.</p>
<p>And again: due to degeneracy, there may be different optimal
primal and dual solutions, so the behavior for a single LP
relaxation and the resulting pricing problem may be different.</p>
<p>Another thing: do you have upper bounds on your variables? Did
you mark them as lazy? Having non-lazy upper bounds on variables
regularly causes issues, because those may have dual values that
you probably don't regard in your pricing problems.<br>
</p>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<div class="WordSection1">
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As far as I know, there are many
researchers using SCIP framework for Branch and Price
algorithm, so I believe there should be a way to resolve this
problem.
<o:p></o:p></p>
<p class="MsoNormal">One thing I tried to do to resolve this
problem is that writing .lp file of RMP within the Pricer
plugin and reading it with CPLEX to solve the LP relaxation
and get the dual solutions. However, it didn’t include the
constraints generated from branching in the parents nodes and
wasn’t able to have the right LP model to solve. <br>
</p>
</div>
</blockquote>
<p>Which constraints are included depends on which method you use to
write the problem. But in general, I would not recommend this, it
should all work with the linked LP solver.</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<div class="WordSection1">
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Long story in short,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">1) I set presolving/maxrestarts = 0 ,
propagating/maxrounds=0 and propagating/maxroundsroot=0 to
get dual solutions, but it is not accurate. What else should I
do to get the correct dual solutions of LP ?
</p>
</div>
</blockquote>
<p>See above. This should also not be needed within the
branch-and-price framework.</p>
<p><br>
</p>
<blockquote type="cite"
cite="mid:CH2PR11MB42156F578AFA39AF338BD665E7B00@CH2PR11MB4215.namprd11.prod.outlook.com">
<div class="WordSection1">
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal">2) Is there a way to use Cplex to solve RMP
LP relaxation within Branch and Price framework?
<o:p></o:p></p>
<p class="MsoNormal">3) Would it be resolved if I install SCIP
with CPLEX as lp solver?<o:p></o:p></p>
</div>
</blockquote>
<p>I don't know if your problem would be resolved, the
branch-and-price framework SCIP should work both with SoPlex and
CPLEX as LP solvers, without any tweaks. But if you install SCIP
with CPLEX as LP solver, all LPs, including the RMP LP
relaxations, are solved with CPLEX.</p>
<p><br>
</p>
<p>Best,<br>
Gerald</p>
<br>
</body>
</html>