<html><body>
<p>Lasse,<br>
<br>
Interesting. Using si->initialSolve() without any options tells Clp to get a solution in what it thinks is the fastest way. With your problem being long and thin, it thinks it can do better than straight simplex. In your case it is using one of two dubious ideas - which it chooses is triggered by whether your problem has more or less than 6000 columns. If it is more then it does repeated simplex solves on small subsets of problem. This causes no problems.<br>
<br>
If it is just less than 6000 columns, it computes an approximate solution and then cleans it up. The approximate solution can have non integral values. Normally these would get cleaned up as reduced costs would be nonzero. In this case they are exactly zero and code can't see why it should move them.<br>
<br>
If you replace the initialSolve by resolve, then the problem goes away. However the long thin strategy is 50 times faster!<br>
<br>
To get good performance and normal simplex characteristics you need to add ten lines. I attach a modified integral.cpp.<br>
<br>
John Forrest<br>
<br>
<br>
<i>(See attached file: integral.cpp)</i><br>
<img width="16" height="16" src="cid:2__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt="Inactive hide details for Lasse Kliemann ---06/23/2009 06:57:55 PM---* Message by -Michael Hennebry- from Tue 2009-06-23:"><font color="#424282">Lasse Kliemann ---06/23/2009 06:57:55 PM---* Message by -Michael Hennebry- from Tue 2009-06-23:</font><br>
<br>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">From:</font></td><td width="100%"><img width="1" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">Lasse Kliemann <lasse-coin-2008@plastictree.net></font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">To:</font></td><td width="100%"><img width="1" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">clp@list.coin-or.org</font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">Date:</font></td><td width="100%"><img width="1" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">06/23/2009 06:57 PM</font></td></tr>
<tr valign="top"><td width="1%"><img width="96" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2" color="#5F5F5F">Subject:</font></td><td width="100%"><img width="1" height="1" src="cid:3__=0ABBFF4CDFA3DEFD8f9e8a93df938@us.ibm.com" border="0" alt=""><br>
<font size="2">Re: [Clp] How to get integral solution for totally unimodular matrix?</font></td></tr>
</table>
<hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br>
<br>
<br>
<tt>* Message by -Michael Hennebry- from Tue 2009-06-23:<br>
> On Tue, 23 Jun 2009, Lasse Kliemann wrote:<br>
> <br>
> >I tried using CLP via 'OsiClpSolverInterface.initialSolve()' to<br>
> >solve a bipartite matching problem, which is known to have a<br>
> >totally unimodular matrix. So, Simplex method should give only<br>
> >integral solutions AFAIK. Indeed, this works well with GLPK's<br>
> >'glp_simplex(...)'. However, CLP on several occasions delivers<br>
> >clearly non-integral solutions. What could be the reason for<br>
> >this? Is there a configuration parameter to change that?<br>
> <br>
> Every basic solution, feasible or not, is integral.<br>
> Any other answer is wrong.<br>
> You are doing smeting wrong or Clp is doing something wrong.<br>
<br>
Let's find out. It is not too easy to reproduce the problem. <br>
Attached is a self-contained example that triggers it. A <br>
bipartite graph is constructed "randomly", then an LP expressing <br>
maximum-cardinality matching is solved. When a non-integral <br>
solution is encountered, it is printed.<br>
<br>
I tested it on 2 machines. Pretty soon after starting, I see <br>
numbers printed to the screen, like:<br>
<br>
0.0133177<br>
0.986682<br>
0.0133177<br>
0.986682<br>
0.0133177<br>
0.986682<br>
0.986682<br>
<br>
The choice of parameter 'p', the edge probability, seems crucial. <br>
For instance, using 'p=0.5' instead of 'p=0.4' does not trigger <br>
the problem.<br>
[attachment "integral.cc" deleted by John J Forrest/Watson/IBM] [attachment "attplxi1.dat" deleted by John J Forrest/Watson/IBM] _______________________________________________<br>
Clp mailing list<br>
Clp@list.coin-or.org<br>
</tt><tt><a href="http://list.coin-or.org/mailman/listinfo/clp">http://list.coin-or.org/mailman/listinfo/clp</a></tt><tt><br>
</tt><br>
<br>
</body></html>