<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (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:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.Section1
{page:Section1;}
-->
</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]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Hi John,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>further testing seems to show my idea is correct.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Instead of updating the lower bound only I should update the
bound & the column solution accordingly (possibly making the solution
primal infeasible). <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>This means I should calculate the new solution as B^{-1} b, i.e.,
as the product of the basis matrix inverse and the new RHS. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I know that getBInvCol returns a column of B^{-1} and its row
elements are in order of the basis variables returned by getBasics(int*).<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Is the order of the columns of getBInvCol somehow changed? <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>If my new right hand side is<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>b' = b - (1, 0, 0 , ..., 0 ), <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>i.e., I reduce the first entry by 1, I don't have to calculate
the multiplication B^{-1} b but instead, my new column solution is<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>x' = x - B^{-1}_1 <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>i.e., the old solution minus the first column of the basis
inverse. I am not sure about the sign though. In practice, it seems that adding
getBInvCol(R) to the solution works. Is this because I'm manipulating the lower
bound? <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>What I do now is the following:<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'> </span><span
style='font-size:10.0pt;font-family:"Courier New"'><o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.enableSimplexInterface(<span
style='color:blue'>true</span>);<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'><o:p> </o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.getBasics(&vecnBasics[0]);<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.startFastDual(2);<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'><o:p> </o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <span
style='color:blue'>for</span>(<span style='color:blue'>int</span> nRow=0;
nRow<solver.getNumRows(); ++nRow) {<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <span
style='color:blue'>if</span>(abs(solver.getRowPrice()[nRow])>gvEPSILON_CONSTRAINT)
{<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.setRowLower(
nRow, solver.getRowLower()[nRow]-1.0 );<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.getBInvCol(nRow,
&vecfBInvCol[0]);<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> _vector<<span
style='color:blue'>double</span>>::const_iterator
itfBInvCol=vecfBInvCol.begin();<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <span
style='color:blue'>for</span>(_vector<<span style='color:blue'>int</span>>::const_iterator
itnBasic=vecnBasics.begin(); itnBasic!=vecnBasics.end(); ++itnBasic,
++itfBInvCol) {<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.getModelPtr()->solutionRegion()[*itnBasic]
+= *itfBInvCol;<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> }<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <span
style='color:blue'>break</span>;<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> }<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> }<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.resolve();<o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> <o:p></o:p></span></p>
<p class=MsoNormal style='text-autospace:none'><span style='font-size:10.0pt;
font-family:"Courier New"'> solver.stopFastDual();<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'> solver.disableSimplexInterface();</span><span
style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I only need the enableSimplexInterface call, because I need to
call getBasics(). If I don't call enableSimplexInterface,
ClpModel::pivotVariable_ is NULL. Is there another solution like setting some
option so the solver keeps pivotVariable_ around? <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Thanks a lot,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Sebastian <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div style='border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'>
<div>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span
style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> Sebastian Theophil <br>
<b>Sent:</b> Dienstag, 21. Juli 2009 17:21<br>
<b>To:</b> 'John J Forrest'<br>
<b>Cc:</b> clp@list.coin-or.org<br>
<b>Subject:</b> RE: [Clp] Problem infeasible after fast dual although only
bound changed?<o:p></o:p></span></p>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>John,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>the problem is solved first and then I reduce the lower bound of
a constraint with dual value > 0.0. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Thus, the previous dual solution is not optimal anymore because
the complementary slackness property is violated. Both dual value and
associated slack are != 0. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>The problem itself is still feasible of course. I have checked
now what fastDual does internally, and although I don't understand why, it
returns "1" to indicate the problem is infeasible which (in my
opininion) it is not. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Maybe fastDual isn't expected to do what I want it to do.
Usually, when the RHS vector b changes, the column solution x_b is updated with
x_b = B^{-1} b. The resulting x_b may be infeasible but the dual solution stays
(dual) feasible. A dual simplex step (or multiple) go back to a primal and dual
feasible solution. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I do not update the column solution though. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Regards<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Sebastian<o:p></o:p></span></p>
</div>
</div>
<!--[object_id=#0342cca8cd3ef743bdaeaa37dbcc7c82#]--><P style="FONT-SIZE: 10pt; FONT-FAMILY: Tahoma,Verdana,Arial">--<BR>Sebastian Theophil (<A href="mailto:stheophil@think-cell.com">stheophil@think-cell.com</A>)<BR>Software Engineer </P><!--[object_id=#think-cell.com#]--><TABLE style="FONT-SIZE: 10pt; FONT-FAMILY: Tahoma,Verdana,Arial" cellSpacing=0>
<TBODY>
<TR>
<TD style="PADDING-RIGHT: 10pt">think-cell Software GmbH</TD>
<TD colSpan=2><A href="http://www.think-cell.com/">http://www.think-cell.com</A></TD></TR>
<TR>
<TD style="PADDING-RIGHT: 10pt">Invalidenstr. 34</TD>
<TD style="PADDING-RIGHT: 5pt">phone</TD>
<TD>+49-30-666473-10</TD></TR>
<TR style="HEIGHT: 20pt" vAlign=top>
<TD style="PADDING-RIGHT: 10pt">10115 Berlin, Germany</TD>
<TD style="PADDING-RIGHT: 5pt">toll-free (US)</TD>
<TD>+1-800-891-8091</TD></TR>
<TR>
<TD colSpan=3>Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl</TD></TR>
<TR>
<TD colSpan=3>Amtsgericht Berlin-Charlottenburg, HRB 85229</TD></TR></TBODY></TABLE></body>
</html>