[Coin-discuss] Questions about OSI - 1

[Laszlo Ladanyi]

Dear Laci and JP,

several days ago, I sent at coin discussion mailing list the following messagge, but actually I don't see it posted in the mailing list neither I recived any news from you.

Shuld I resend the msg? Do you need some explanation about it?

Thank you,
Luigi

-----Messaggio Originale----- 
Da: Poderico Luigi 
A: coin discussion 
Data invio: lunedì 21 maggio 2001 11.27
Oggetto: Re: [Coin-discuss] Questions about OSI


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.

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.

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.

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.

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.
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>

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.

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?

We hope that you'll find our suggestions and proposal interesting as we
found your answers.

Thank you,

Antonio Frangioni
Luigi Poderico