[Coin-discuss] Questions about OSI - 2

[Laszlo Ladanyi]

Hi Luigi,

Here are my opinions.

On Tue, 26 Jun 2001, Luigi Poderico wrote:

> 
> Laci and JP,
> 
> we have checked out the development branch of the code, finding many
> answers to our questions. Yet, we have some other notes about OSI.
> 
> 1) The methods returning the status of the solution computation
> (isAbandoned(), etc.) could be extended with the following: 1) feasible but
> not integer feasible; 2) feasible but not integer feasible because the
> solver had reached the maximum number of LPs or QPs calls; 3) infeasible
> since relaxed problem is infeasible; 4) integer feasible and possible
> suboptimal, because the solver had reached the maximum number of LPs or QPs
> calls.

This could certainly be added. So far we were working mainly on the LP part,
even setting vars to integer/continuous has been added only recently.
(Yesterday for cplex :-)

> 
> 2) We think that the method returning the solver status should be
> something like this:
> 
> <code>
> enum OSISolverStatus { isAbandoned = 0, isProvenOptimal, ... ,
> lastFreeSolverStatus};
> virtual int GetStatus() = 0; /* not virtual OSISolverStatus GetStatus() = 0
> */
> <\code>
> 
> This should be grant any solver implementation to get back its owns status,
> using lastFreeSolverStatus as the first new status and thanks the int of
> GetStatus() that allow to return any OSISolverStatus and any other enums.
> 

We did a lot of thinking how status reporting should be implemented, with an
enum and a getStatus() as you suggest or with separate functions as we did it.
We chose the latter, because there can be multiple stati that are valid. E.g.,
you can have proofs that both the primal and the dual problems are infeasible.
If we introduce stati returned for solving IPs then the number of
possibilities (when you can prove multiple stati) increases a lot. Granted, it
is much nicer just to call getSatus() and make a switch on the result, but
we felt the current implementation is more precise. Still, it's not impossible
to have multiple ways of reporting the status (though it can be confusing) and
then everyone can use whichever they feel comfortable with.

> Further, for the same reason we suggest to change the methods
> <code>
> virtual bool setIntParam(OsiIntParam key, int value)
> virtual bool setDblParam(OsiDblParam key, double value)
> virtual bool getIntParam(OsiIntParam key, int& value)
> virtual bool getDblParam(OsiDblParam key, double& value)
>   <\code>
> in
> <code>
> virtual bool setIntParam(int key, int value)
> virtual bool setDblParam(int key, double value)
> virtual bool getIntParam(int key, int& value)
> virtual bool getDblParam(int key, double& value)
> <\code>
> 
> This would allow derived solvers to re-use the methods for setting/getting
> their specific parameters together with the "standard" ones.
> 

Could you explain this a bit more? If I understand your point correctly then
you suggest this change so that the solvers could just simply pass the
arguments to their internal routines without having to switch. However, the
value of key can be different for different solvers even if it serves the same
purpose. Thus in essence we'd have to choose the keys of one solver and let
the others map everything, but that wouldn't be solver agnostic (or
politically correct :-). We felt it's better if everyone has to do the
mapping. Also, this way we can eventually get to the point where the Osi
parameter list is a sort of union of all the parameter lists and the solvers
can accept or reject any. Let me know if I misunderstood you.

> 3) It's not obvious what the index of the new column and new row added
> respectively by addCol() and addRow() is. Maybe, a general solution could be
> to return the index of the new column/row.
> It's not obvious what happen when a column/row is deleted, too. In fact the
> solvers has several different strategies, such as: 1) do nothing, the
> next new column/row will fill the hole; 2) compact the matrix shifting to
> left/up the columns/rows on the right/bottom; 3) compact the matrix moving
> the last column/row to the hole.
> So, either the strategy is decided in the interface, and all the solvers
> have to comply (but this could make it very difficult to use some specific
> solver), or a method must be provided returning the strategy used by the
> solver.
> 

This is a very good point. It should be specified in the interface how things
are done. The problem is that I don't think any solver returns the index of
the added col/row. Personally I just always assumed that they are just
appended to the end. As for deletion I always assumed that solvers compact the
matrix. Note that this compaction (is this a word? :-) need not physically
occur, just the indexing of the rows/cols behind needs to be shifted. In any
case I don't think any solver ever fills the gaps with new rows/cols added
later.

> 4) Looking the code of OsiPackedVectorBase we have found some methods
> returning objects of class OsiPackedVector. Now the problem is that
> OsiPackedVector derive by  OsiPackedVectorBase!!! There are several reasons
> to avoid this, but the main is that the compiler doesn't know the
> sizeof(OsiPackedVector) while it compile OsiPackedVectorBase.
> All the methods binaryOp() compile correctly because they are templates and
> so effectively compiled when they are instantiated.

You caught me exploiting a loophole in the C++ specification :-)

> What do you think to change the signature of binaryOp()'s family as the
> following?
> <code>
> template <class BinaryFunction>
> void binaryOp(double value, BinaryFunction bf, OsiPackedVectorBase& ret)
> const;
> 
> template <class BinaryFunction> void
> binaryOp(BinaryFunction bf, double value, OsiPackedVectorBase& ret) const;
> 
> template <class BinaryFunction> void
> binaryOp(const OsiPackedVectorBase& op2, BinaryFunction bf,
> OsiPackedVectorBase& ret) const
> <\code>

I have no problem with that. In fact, it'd be probably much more efficient
because of using a reference and not passing the packed vector by value.

> 
> And now our extension proposal of OSI.
> 
> 1) As in the Standard Template Library, we are thinking to add to OSI
> library a '#1' file for each '*.hpp' file. For example, to add to OSI lib.
> the file 'OSISolverInterface' that will look something like:
> 
> <code>
> #define OSINAMESPACEUSING
> namespace OptimizationSolverInterface {
> using namespace ::std; // for stl stuff
> #include "OSISolverInterface.h"
> }; // namespace
> <\code>
> 
> Alternatively, we could simply add
> 
> #ifdef OSINAMESPACEUSING
>   namespace OptimizationSolverInterface {
> #endif
> 
> etc. in the .hpp files, and the corresponding
> 
> #ifdef OSINAMESPACEUSING
>   using namespace OptimizationSolverInterface;
> #endif
> 
> in the .cpp files. Namespaces are not very often useful, but the day in
> which you suddenly find yourself in need of them you may harshly regret
> not having used them.

This question came up before in the design phase and we chose to prefix
everything with Osi, which is sort of namespacing. On the other hand I don't
see any reason why we couldn't add namespaces as well.

> 
> 2) In order to add the quadratic objective function, we would like to add
> the following methods distinguishing two cases: generic symmetric quadratic
> matrix and diagonal quadratic matrix. All the methods have a default
> implementation that throw an exception like "the solver is unable to solve
> quadratic problem". The idea is that a LP is just the special version of a
> QP with 0 Hessian; any new variable that is created has the corresponding
> column of the Hessian set to 0, unless explicitly set with the methods below.
> <code>
> /** Set the cost quadratic matrix to the quadMatrix and switches the current
> problem to a quadratic one. All the values in quadMatrix will be copied.
> If quadMatrix==NULL then the quadratic matrix will be freed and the current
> problem is switched to a linear ones.
> */
> virtual void setQuadraticMatrix(const OsiPackedMatrix* quadMatrix);
> 
> /** Set the cost quadratic matrix to the matrix having diagQuadMatrix on the
> diagonal and zeros elsewhere, switches the current problem to a quadratic
> one. All the values in diagQuadMatrix will be copied.
> If diagQuadMatrix==NULL then the quadratic matrix will be freed and the
> current problem is switched to a linear ones.
> */
> virtual void setQuadraticMatrix(const OsiPackedVector* diagQuadMatrix);
> 
> /** Set a row (and column) of cost quadratic matrix.
> */
> virtual void setQuadraticMatrix(int rowIndex, const 
> OsiPackedVector& newRowColumn);
> 
> /** Set a diagonal element of cost quadratic matrix.
> */
> virtual void setQuadraticMatrix(int index, double newDiagonalElement);
> 
> /** Set a generic element of cost quadratic matrix.
> */
> virtual void setQuadMatrixElem(int row, int col, double qElem) const;
> 
> /** Get a generic element of cost quadratic matrix.
> */
> virtual double getQuadMatrixElem(int row, int col) const;
> <\code>
> 
> We think that the above methods are a minimal and complete subset of
> operations to work with quadratic problem. Now the problem is: where we put
> these methods? We have two proposals:
> 
> Proposal 1 - Extend directly the class OsiSolverInterface. All the
> "quadratic" methods have a default implementation, so any class derived from
> OsiSolverInterface can be left unchanged. The problem is that when someone will
> extend a derived class (such as OsiCpxSolverInterface) to the 
> quadratic case, the good practice impose a test to all the software 
> involved with OsiCpxSolverInterface.
> 
> Proposal 2 - Derive a new class OsiQPSolverInteface from OsiSolverInterface
> with the "quadratic" methods. The disadvantage is due to the code
> duplication, i.e., the class OsiQPCpxSolverIntarface will be very similar to
> OsiCpxSolverInterface. Note that a multiple derivation is improper: any
> change in OsiCpxSolverInterface impose a test to all the software involved
> with OsiQPCpxSolverIntarface too.
> 
> We haven't enough information and feeling with OSI and COIN library to make
> an appropriate choice. Have you some suggestions? Is there some other
> solution?

Actually, the same question arose already and if I remember well, we decided
to derive a new class. What's more we were thinking on deriving separate
classes for simplex based on non-simplex based LP solvers and maybe a higher
level class for IP solvers.

> 
> We hope that you'll find our suggestions and proposal interesting as we
> found your answers.
> 
> Thank you,
> 
> Antonio Frangioni
> Luigi Poderico
> 

Your observations and proposals are very good and I'm happy you took the time
to go through the code.

Hope to hear from you soon,
--Laci