[Coin-discuss] Quadratic costs in OSI?

[Matthew Saltzman]

On Mon, 13 Jun 2005, Antonio Frangioni wrote:

> I'll see if I can have a programmer taking care of this. At most I'll be 
> able to provide Xxx \in \{ `Clp' , `Cpx' \}. However, the delicate thing 
> will be deciding the exact shape of the interface. When I'll be able to 
> start (which won't be tomorrow) I'll post one proposal for upgrading the 
> OSISolver interface. What may be nice to know beforehand is whether a 
> solution which simply adds the methods to the general interface is 
> considered good by the community, or one should plan an extension of the 
> hyerarchy. In other words: is it OK for everybody that *every* OSISolver 
> is, in general, a QP solver, except that some may refuse to implement 
> the QP-specific methods throwing an exception? Or a cleaner but more 
> cumbersome solution where a OSIQPSolver deriving (??) from OSISolver is 
> required? In the latter case, what should be the actual inheritance 
> diagram? I'm thinking e.g. to how OsiSimplexInterface enters the picture 
> (since QP-simplex is also in the cards ...).

Separation of QP functionality from the current OSI is a Good Thing.

It seems like the natural hierarchy is to extend the OsiSolverInterface 
base class with OsiQpSolverInterface, which adds base-class versions of 
calls necessary to support QP (not simplex-specific ones though--see 
later).  Then OsiXxxQpSolverInterface would be derived from 
OsiXxxSolverInterface and OsiQpSolverInterface.  You could derive 
OsiQpSimplexInterface from OsiSimplexInterface and a solver that supports 
QP simplex would be derived from that as well.

Now this is a diamond-shaped inheritance, but we think it is pretty clean 
as long as OsiQpSolverInterface only adds to OsiSolverInterface and 
doesn't override anything in it.  Then OsiXxxQpSolverInterface should only 
override members of OsiQpSolverInterface and get everything defined in 
OsiXxxSolverInterface from the parent class.

Because of the diamond, the inheritance from OsiSolverInterface needs to 
be virtual for all OsiXxxSolverInterface classes.  There's a performance 
penalty for doing that, but we don't think it will be significant compared 
to the cost of doing the math in the algorithm.

Currently, OsiSolverInterface and OsiSimplexInterface are not 
hierarchically related.  The OsiClpSolverInterface inherits from both, and 
at the moment CLP is the only simplex-aware solver.  If 
OsiQpSimplexInterface inherits from OsiSimplexInterface, then inheritance 
from OsiSimplexInterface has to be virtual as well, though.  Again, it 
would be best for OsiQpSimplexInterface to only extend, not override, 
OsiSimplexInterface.

> More in general, I think this raises the question as to whether 
> OSISolver will ever become an interface for (nonlinearly constrained?) 
> nonlinear problems solvers, and in this case if the current shape of the 
> interface is suitable for the task. But with this I'm surely slipping 
> into the realm of far away dreams and I definitely stop here.

The current interface isn't really well-suited for this kind of extension. 
There are two directions to go here.  One is NLPAPI (another COIN-OR 
project designed to interface to nonlinear solvers).  The other is the 
next version of OSI, which is currently in development, and which is 
designed with extensibiliity in mind in a way that the current OSI was 
not.

I have a mailing list for the next OSI: 
http://list.coin-or.org/mailman/listinfo/coin-osi-devel.  I haven't done 
anything with it yet, but if you join up, I'll be discussing some issues 
there as development proceeds.

-- 
 		Matthew Saltzman

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