<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)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<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-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'>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>
<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"'> John J Forrest
[mailto:jjforre@us.ibm.com] <br>
<b>Sent:</b> Dienstag, 21. Juli 2009 16:40<br>
<b>To:</b> Sebastian Theophil<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 style='margin-bottom:12.0pt'>Sebastian,<br>
<br>
It seemed to work when I tried something similar, but my problem was feasible
after changes - duals did change with (2) but not with (0). You say the result
is infeasible. The duals are not updated if infeasible. fastDual was meant to
do as little as possible.<br>
<br>
John Forrest<br>
<br>
<img width=16 height=16 id="_x0000_i1025"
src="cid:image001.gif@01CA0A22.D7845420"
alt="Inactive hide details for "Sebastian Theophil" ---07/21/2009 10:32:24 AM---Hi John,"><span
style='color:#424282'>"Sebastian Theophil" ---07/21/2009 10:32:24
AM---Hi John,</span><o:p></o:p></p>
<table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1026"
src="cid:image003.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>From:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1027"
src="cid:image004.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt'>"Sebastian Theophil"
<stheophil@think-cell.com></span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1028"
src="cid:image003.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>To:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1029"
src="cid:image004.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt'>John J Forrest/Watson/IBM@IBMUS</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1030"
src="cid:image003.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>Cc:</span><o:p></o:p></p>
</td>
<td width="100%" style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1031"
src="cid:image004.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt'><clp@list.coin-or.org></span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1032"
src="cid:image003.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>Date:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1033"
src="cid:image004.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt'>07/21/2009 10:32 AM</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1034"
src="cid:image003.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>Subject:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1035"
src="cid:image004.png@01CA0A22.D7845420"><br>
<span style='font-size:10.0pt'>RE: [Clp] Problem infeasible after fast dual
although only bound changed?</span><o:p></o:p></p>
</td>
</tr>
</table>
<div class=MsoNormal>
<hr size=2 width="100%" noshade style='color:#8091A5' align=left>
</div>
<p class=MsoNormal><br>
<br>
<br>
<span style='font-family:"Calibri","sans-serif";color:#1F497D'>Hi John,</span><br>
<br>
<span style='font-family:"Calibri","sans-serif";color:#1F497D'>thanks for your
prompt reply. Unfortunately it doesn't work no matter what parameters I pass. I
have also updated to the most recent TRUNK to make sure I'm not finding old bugs.
</span><br>
<span style='font-family:"Calibri","sans-serif";color:#1F497D'>Still, the duals
don't get updated and the result is infeasible. </span><br>
<br>
<span style='font-family:"Calibri","sans-serif";color:#1F497D'>Regards</span><br>
<span style='font-family:"Calibri","sans-serif";color:#1F497D'>Sebastian</span><br>
<br>
<br>
<b><span style='font-family:"Tahoma","sans-serif"'>From:</span></b><span
style='font-family:"Tahoma","sans-serif"'> John J Forrest [<a
href="mailto:jjforre@us.ibm.com">mailto:jjforre@us.ibm.com</a>] <b><br>
Sent:</b> Dienstag, 21. Juli 2009 16:14<b><br>
To:</b> Sebastian Theophil<b><br>
Cc:</b> clp@list.coin-or.org; clp-bounces@list.coin-or.org<b><br>
Subject:</b> Re: [Clp] Problem infeasible after fast dual although only bound
changed?</span><o:p></o:p></p>
<p><span style='font-size:13.5pt'>Sebastian,<br>
<br>
If you want the duals updated then it should be startFastDual(2) - see
OsiClpSolverInterface.hpp;<br>
<br>
John Forrest<br>
<br>
</span><img border=0 width=16 height=16 id="_x0000_i1037"
src="cid:image001.gif@01CA0A22.D7845420"
alt="Inactive hide details for "Sebastian Theophil" ---07/21/2009 07:33:45 AM---Hi, I have a very simple primal degenerate LP proble"><span
style='font-size:13.5pt;color:#424282'>"Sebastian Theophil"
---07/21/2009 07:33:45 AM---Hi, I have a very simple primal degenerate LP
problem:</span> <o:p></o:p></p>
<table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td width="20%" valign=top style='width:20.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='color:#5F5F5F'><br>
From:</span><o:p></o:p></p>
</td>
<td width="80%" valign=top style='width:80.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><br>
"Sebastian Theophil" <stheophil@think-cell.com><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="20%" valign=top style='width:20.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='color:#5F5F5F'><br>
To:</span><o:p></o:p></p>
</td>
<td width="80%" valign=top style='width:80.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><br>
<clp@list.coin-or.org><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="20%" valign=top style='width:20.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='color:#5F5F5F'><br>
Date:</span><o:p></o:p></p>
</td>
<td width="80%" valign=top style='width:80.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><br>
07/21/2009 07:33 AM<o:p></o:p></p>
</td>
</tr>
<tr>
<td width="20%" valign=top style='width:20.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='color:#5F5F5F'><br>
Subject:</span><o:p></o:p></p>
</td>
<td width="80%" valign=top style='width:80.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><br>
[Clp] Problem infeasible after fast dual although only bound changed?<o:p></o:p></p>
</td>
</tr>
<tr>
<td width="20%" valign=top style='width:20.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='color:#5F5F5F'><br>
Sent by:</span><o:p></o:p></p>
</td>
<td width="80%" valign=top style='width:80.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><br>
clp-bounces@list.coin-or.org<o:p></o:p></p>
</td>
</tr>
</table>
<div class=MsoNormal>
<hr size=2 width="100%" noshade style='color:#A0A0A0' align=left>
</div>
<p class=MsoNormal><br>
<span style='font-size:13.5pt'><br>
<br>
</span><span style='font-family:"Courier New"'><br>
Hi,<br>
<br>
<br>
I have a very simple primal degenerate LP problem:<br>
<br>
\Problem name: <br>
<br>
Minimize<br>
obj: x2<br>
Subject To<br>
cons0: x0 + x2 >= -0<br>
cons1: - x0 + x2 >= -10<br>
cons2: x1 + x2 >= -0<br>
cons3: - x1 + x2 >= -10<br>
Bounds<br>
x0 Free<br>
x1 Free<br>
x2 Free<br>
End<br>
<br>
The primal solution is (5, 5, -5), but there are two dual solutions<br>
(0.5, 0.5, 0, 0) and (0, 0, 0.5, 0.5). <br>
The code below reads the file, searches a dual positive variable and<br>
changes the RHS of the associated constraint. The constraint can no<br>
longer be binding, and the dual solution should change solution after a<br>
resolve. This works as expected without startFastDual. <br>
<br>
If startFastDual is active, the dual solution doesn't change though<br>
although it is no longer feasible. <br>
<br>
OsiClpSolverInterface solver;<br>
solver.readLp("C:\\primaldegenerate1.lp");<br>
solver.initialSolve();<br>
<br>
solver.startFastDual(0);<br>
<br>
int nRow=0;<br>
for(; nRow<solver.getNumRows(); ++nRow) {<br>
<br>
if(abs(solver.getRowPrice()[nRow])>gvEPSILON_CONSTRAINT) {<br>
break;<br>
}<br>
}<br>
<br>
solver.setRowLower( nRow, solver.getRowLower()[nRow]-1.0<br>
);<br>
solver.resolve();<br>
solver.stopFastDual();<br>
<br>
<br>
Is this a bug or am I doing sth wrong? I thought bound changes inside<br>
fast dual were allowed. What would be the fastest way to resolve the<br>
system after such a change? <br>
<br>
<br>
Thanks,<br>
Sebastian<br>
<br>
--<br>
Sebastian Theophil . stheophil@think-cell.com<br>
Software Engineer<br>
<br>
think-cell Software GmbH . Invalidenstr. 34 . 10115 Berlin, Germany <u><span
style='color:blue'><br>
</span></u></span><a href="http://www.think-cell.com/"><span style='font-family:
"Courier New"'>http://www.think-cell.com</span></a><span style='font-family:
"Courier New"'> . phone +49-30-666473-10 . toll-free (US) +1-800-891-8091<br>
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl . Amtsgericht
Berlin-Charlottenburg, HRB 85229<br>
<br>
<br>
_______________________________________________<br>
Clp mailing list<br>
Clp@list.coin-or.org<u><span style='color:blue'><br>
</span></u></span><a href="http://list.coin-or.org/mailman/listinfo/clp"><span
style='font-family:"Courier New"'>http://list.coin-or.org/mailman/listinfo/clp</span></a><o:p></o:p></p>
<p><span style='font-family:"Tahoma","sans-serif"'>--<br>
Sebastian Theophil (</span><a href="mailto:stheophil@think-cell.com"><span
style='font-family:"Tahoma","sans-serif"'>stheophil@think-cell.com</span></a><span
style='font-family:"Tahoma","sans-serif"'>)<br>
Software Engineer </span><o:p></o:p></p>
<table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0>
<tr>
<td width=146 style='width:109.5pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>think-cell
Software GmbH</span><o:p></o:p></p>
</td>
<td width=186 colspan=2 style='width:139.5pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><a href="http://www.think-cell.com/"><span
style='font-family:"Tahoma","sans-serif"'>http://www.think-cell.com</span></a><o:p></o:p></p>
</td>
</tr>
<tr>
<td width=146 style='width:109.5pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>Invalidenstr.
34</span><o:p></o:p></p>
</td>
<td width=76 style='width:57.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>phone</span><o:p></o:p></p>
</td>
<td width=108 style='width:81.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>+49-30-666473-10</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width=146 valign=top style='width:109.5pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>10115
Berlin, Germany</span><o:p></o:p></p>
</td>
<td width=76 valign=top style='width:57.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>toll-free
(US)</span><o:p></o:p></p>
</td>
<td width=108 valign=top style='width:81.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>+1-800-891-8091</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width=332 colspan=3 style='width:249.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>Directors:
Dr. Markus Hannebauer, Dr. Arno Schoedl</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width=332 colspan=3 style='width:249.0pt;padding:0in 0in 0in 0in'>
<p class=MsoNormal><span style='font-family:"Tahoma","sans-serif"'>Amtsgericht
Berlin-Charlottenburg, HRB 85229</span><o:p></o:p></p>
</td>
</tr>
</table>
<p style='margin-bottom:12.0pt'><o:p> </o:p></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>