[Coin-discuss] Open Source Simplex solver?

[John J Forrest]

Antonio,

>Since we are all talking OOP, I would suggest to structure the code by
>separating the matrix operations from the rest. What I have in mind is
>a basic Simplex class which implements the standard parts of the
>algorithm, plus the pricings, with all the methods for base manipulation
>virtual. This base class should not know, or assume, anything about the
>structure of the coefficient matrix, which should be taken care of by
>the derived classes.

That is a good idea.  Originally I had intended to do so, but then I
thought I would try and put up a very basic solver to get reaction.  Due to
IBM stuff I have had more time to work on dual simplex solver, so I have
done the coding you suggested.  In my case the idea was to allow very large
air crew scheduling problems where number of rows is <32000 and all entries
are 1, which I could store much more compactly.  Also for column generation
techniques.

For Simplex we may need to scale problem.  To keep flexibility I have kept
the scaling factors separate so they are applied when needed.  The overhead
is not too bad and then I can play with dynamic scaling.

The abstract base class is ClpMatrixBase.  The only implementation at
present is ClpPackedMatrix  which assumes structure is OsiPackedMatrix.
Most of the code deals with Simplex stuff such as creating a basis to be
factorized and scaling the matrix.
John