[Coin-discuss] Questions about OSI

[Laszlo Ladanyi]

Hi Luigi,

First of all, there is a development branch of the code that you can check out
with cvs:
  cvs checkout -r devel Osi

That branch will answer many of your questions. Also, we are in the process of
deriving a new class, OsiSimplexSolverInterface, that will have simplex
specific virtual methods in it.

On Sun, 22 Apr 2001, Luigi Poderico wrote:

> Hi to all.
> 
> We were planning to develop a C++ common interface for (mixed integer)
> linear and quadratic optimization solvers. Looking on the net, we found the
> web-pages of COIN. We would like to extend the OSI interface in order to
> accomplish our goal.
> 
> Before to start, we wolud like to understand better the design of OSI and so
> we have some questions:
> 
> 1) Before finding OSI, we thought to have two main abstract classes in our
> interface: a class Problem for a generic linear/quadratic problem, with a
> set of operations to create, modify and read the data of the problem and
> solution, and a class Solver for a generic linear/quadratic solver, with a
> set of operation to solve and get some information about the problem (e.g.
> empty or unbound problem, etc.). We think that this approach may be
> beneficial, e.g. allowing to pass the same problem to different solvers, or
> to use the same solver for different problems. So the first questions that
> we have is about your choice to have an unique class for the problem and the
> solver: what are the reasons that suggested (or imposed) you to have an
> unique class?

The reason is that we have designed OSI to be a uniform API for other solvers,
with LP solvers being the foremost in our minds. (Still the current design is
OK for a larger class of problems, e.g., QP) The existing commercial LP
solvers keep their own copy of the problem. If we had separated the interfaces
of defining the problem and solving the problem that would have created either
inefficiency problems (in terms of wasting lot of memory) or we'd have had to
create the OSL / CPLEX / XPRESS / etc. interface with multiple inheritance
which would almost be the same as a single interface. Also, it wasn't well
supported at the time we started. So we decided to go for a single interface.

> 
> 2) Is there a way to know if the solver had found a solution? And if the
> problem haven't solution is there a way to get more information about that?

First question: yes in the devel branch. Second question: sort of in the devel
branch. If the problem is primal (dual) infeasible then there is a method
defined that returns a dual (primal) ray proving the infeasibility. I suppose
more information could be extracted, we are just not sure what. Suggestions?

> 
> 3) Is there a way to set the parameters of the differents solver
> implementation via the abstract class?

Yes in the devel branch. Actually, it's just a first try to set parameters.
What we thought would be the best (and started the implementation) is to
include almost every parameter of every solver... and let the individual
solver interfaces sort out what to make of a parameter if they are asked to
set the parameter. Granted, this may not be the best solution, but we couldn't
come up with anything better. After all, all solvers use different parameters. 

> 
> 4) Why don't you use the namespace construct to avoid the OSI prefix?
> 

Not all compilers are equally happy with namespaces. Also, we felt that having
the prefix there makes it more obvious in the code that now there is a call to
a method in OSI. I guess this is more of a personal preference than anything
else... :-)

> 5) Don't you think that the c++-style std::vector<double> should be
> preferred to the c-style vector double*?

For efficiency reasons, not at the moment. We took a hard look of the assembly
code generated by gcc when the STL vector class was used. It was *much* longer
than the code generated for double*. When you iterate through v[i], and v is a
vector then the code is much slower. Note that this wouldn't have affected
calls to the STL, since there always iterators are passed and the iterators
are effectively double*'s.

> 
> In order to have the OSI interface to perform all the tasks we need, we are
> planning to extend it in the following ways:
> 
> 1) extend the objective function to the quadratic case;

That would be great! Actually, As I noted on the top, we are working on a
simplex solver interface. Maybe the qp solver should be derived from the base
solver interface? what do you think?

> 
> 2) extend the set of problem modification methods to cover all the possible
> medifications (addition and deletion of columns/rows, change of
> costs/RHS/bounds/constraints coefficients/variable types).

this is already done in the devel branch.

> 
> 3) improve the output routines and the error handling system to report
> unfeasible/unbounded problems and the like

this is mostly done in the devel branch, though probably can be improved...

> 
> 4) add namespaces.

We can probably switch to namespaces, or rather, have a compile time switch to
control whether prefixes or namespaces are used (thus avoiding a religious 
war :-).

> 
> We would really appreciate observations, comments and suggestions about our
> proposed extensions. We are especially concerned about maximizing the
> possibility of having our modified version to reach the distribution point,
> so that all other users can benefit from them.

Agreed :-). It seems your additions would be worthwhile. If you decide that
you'd like to build upon OSI and do it, then when your code is ready it'd go
into a devel branch first then into the main distro. At that point you'd
become the maintainer of that part, probably with write access to the CVS tree
(since the contribution seems to be large enough).

> 
> Best regards,
> 
> Antonio Frangioni, assistant professor Dip. Informatica Università di Pisa,
> frangio at di.unipi.it
> Luigi Poderico, freelance, lupoderi at tiscalinet.it
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at oss.software.ibm.com
> http://oss.software.ibm.com/developerworks/opensource/mailman/listinfo/coin-discuss
> 

Thanks for your interest!
--Laci
  ladanyi at us.ibm.com