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

[Matthew Saltzman]

John-

Interesting.  So the long, thin solver need not terminate with a BFS if
there are multiple optima?

Does the interior-point solver have a sanitizer that generates a BFS
from an interior solution?  Could it be applied in this situation?

		Matt

On Wed, 2009-06-24 at 05:20 -0400, John J Forrest wrote:
> 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)
> Inactive hide details for Lasse Kliemann ---06/23/2009 06:57:55 PM---*
> Message by -Michael Hennebry- from Tue 2009-06-23:Lasse Kliemann
> ---06/23/2009 06:57:55 PM---* Message by -Michael Hennebry- from Tue
> 2009-06-23:
> 
> 
> 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
> 
> 
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
-- 
                Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs