[Clp] How to get integral solution for totally unimodular matrix?

[John J Forrest]

Lasse,

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.

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.

If you replace the initialSolve by resolve, then the problem goes away.
However the long thin strategy is 50 times faster!

To get good performance and normal simplex characteristics you need to add
ten lines.  I attach a modified integral.cpp.

John Forrest


(See attached file: integral.cpp)

                                                                                              
  From:       Lasse Kliemann <lasse-coin-2008 at plastictree.net>                                
                                                                                              
  To:         clp at list.coin-or.org                                                            
                                                                                              
  Date:       06/23/2009 06:57 PM                                                             
                                                                                              
  Subject:    Re: [Clp] How to get integral solution for totally unimodular matrix?           
                                                                                              





* Message by -Michael Hennebry- from Tue 2009-06-23:
> On Tue, 23 Jun 2009, Lasse Kliemann wrote:
>
> >I tried using CLP via 'OsiClpSolverInterface.initialSolve()' to
> >solve a bipartite matching problem, which is known to have a
> >totally unimodular matrix. So, Simplex method should give only
> >integral solutions AFAIK. Indeed, this works well with GLPK's
> >'glp_simplex(...)'. However, CLP on several occasions delivers
> >clearly non-integral solutions. What could be the reason for
> >this? Is there a configuration parameter to change that?
>
> Every basic solution, feasible or not, is integral.
> Any other answer is wrong.
> You are doing smeting wrong or Clp is doing something wrong.

Let's find out. It is not too easy to reproduce the problem.
Attached is a self-contained example that triggers it. A
bipartite graph is constructed "randomly", then an LP expressing
maximum-cardinality matching is solved. When a non-integral
solution is encountered, it is printed.

I tested it on 2 machines. Pretty soon after starting, I see
numbers printed to the screen, like:

0.0133177
0.986682
0.0133177
0.986682
0.0133177
0.986682
0.986682

The choice of parameter 'p', the edge probability, seems crucial.
For instance, using 'p=0.5' instead of 'p=0.4' does not trigger
the problem.
[attachment "integral.cc" deleted by John J Forrest/Watson/IBM] [attachment
"attplxi1.dat" deleted by John J Forrest/Watson/IBM]
_______________________________________________
Clp mailing list
Clp at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/clp

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090624/303982a2/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090624/303982a2/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ecblank.gif
Type: image/gif
Size: 45 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090624/303982a2/attachment-0001.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: integral.cpp
Type: application/octet-stream
Size: 2427 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090624/303982a2/attachment.obj>