[Coin-discuss] Gomory cuts and possible Open Source plans - anyone want an Open Source simplex solver?

[John J Forrest]

Having some spare time, I have implemented Gomory cuts in Cgl.  This needed
the ability to get rows and columns of the tableau.  There were two
possibilities:

1) Find the required calls in the various supported solvers.
2) Write an Open Source Factorization module.

I chose the second which is now in as OsiFactorization.  About six years
ago I was trying to implement a parallel simplex solver and wrote a
factorization class.  I have taken this class, simplified it (although it
could do with even more simplification) and allowed it to use
OsiPackedMatrix etc etc.

In order to test the code, I then needed to check if the solution handed to
the Gomory cut module was optimal so I wrote some test coding for that.

At about that stage I realized that if I did not stop soon I would have a
simplex solver!

So I wish to announce that if there is interest I will organize an effort
to develop such a solver.  There are existing Open Source solvers, but the
ones I know about are under the GPL licence which makes it difficult to
build commercial applications incorporating the solver - we would release
this under the CPL licence.  Also we need "adequate" performance on large
problems - on some large problems OSL is a thousand times faster than some
other solvers and my target would be to provide a solver which is no slower
than a factor of 5 when compared to the best available simplex solvers.  I
would not aim for much better than that as the coding can get ugly.

Robin and I have started the bureaucratic process of getting approval from
IBM as there are some issues as to whether IBM employees should be helping
with a possible competitor to OSL.  However we think we should get
approval.  It may take a month or two, so I would like to start the
discussion now to be ready to spring into action.

So -:

Is anyone interested?
In what capacity would they help?
Should it be OsiNativeSolverInterface in the same way as
OsiCpxSolverInterface?  Or is it better to treat it like an algorithm e.g.
Volume?
What about messages (this is a general question as COIN matures - we need
standards)?
How innovative should it be?

If there is interest I can try and get a dual simplex ready which can solve
all netlib test set.   I will try not to invest so much effort that it will
hurt to throw it away and start again.  However I think it important to
have something concrete to react against.

Please post replies to coin-discuss - thanks.  Also if you know someone who
may not subscribe to coin-announce, but who might be interested, please
forward this.

John Forrest