[Coin-discuss] Osi redesign

[Bertrand LECUN]

On Mon, Nov 12, 2001 at 08:27:10PM -0500, Mikhail Nediak wrote:
> Hi,
Hi,

> 
> I think there was also a proposition to separate model components from the
> solver. This a nice way to think about new design from the methodological
> point of view. Also, this would allow us to incorporate different types of
> models and solvers into the same framework in the future.
I follow Mikhail in the idea to separate the model form components from the solver.
But (Maybe i could not cite this company here) Ilog has choosen another design
for their software. 
1- you define a model
2- you "compile" or "generate" the model to produce a new class for LP or for
Constraint programming.

This could be used here 
1- you define your model
2- you produce a new class with the model and the choosen method to it.
> 
> > The whole class structure should be very hierarchical with the constraint
> > types and objective types on the bottom:
> > OsiLinearConstraint, OsiLinearObjective, OsiQuadraticObjective, etc.
> > These classes define the constraint structure and the objective structure and
> > define how to modify them.
> We could define abstract classes OsiObjective and OsiConstraint and then 
> class OsiLinearObjective : public OsiObjective
> class OsiQuadraticObjective : public OsiObjective
> class OsiLinearConstraint : public OsiConstraint
> class OsiIntegralityInfo : public OsiConstraint
> 
> One could, in fact, think of OsiVariable class instead and store domain
> info such as bounds and integrality with it, but I am not sure it is a
> better solution.
I would to have a notion of OsiVariable. without it we could be quite difficult
to implement easily column/constraint generation (Branch and Price/Cut).
>  
> > >From these one can piece together other classes:
> > class OsiLP : public OsiLinearConstraint, public OsiLinearObjective;
> > class OsiQP : public OsiLinearConstraint, public OsiQuadraticObjective;
> > These classes contain what can be done with an LP; most likely, it'll be the
> > solve() method :-).
> There could be a class OsiModel instead that would include a set of
> OsiConstraint's and OsiObjective by composition as opposed to inheritance.
> 
> These guys would, instead, inherit from an abstract OsiSolver that takes
> OsiModel as an input. When handed in model components that they can't
> handle, they would through an exception.
Yes, i agree.
The exception could be replaced choosing the good type in the parameter of the solve
method. This design avoids to give a bad type model in a solver class
> 
> > class OsiLPSimplexPrimal : public OsiLPSimplex;
> > class OsiLPSimplexDual : public OsiLPSimplex;
> > 
> > Along these inheritances each class would declare only those methods that any
> > object of that type should know. Say, getting a row of the tableau works for
> > both primal and dual simplex, but getting a primal ray not necessarily. Many
> > (if not all) of the methods will be pure virtual.
> > 
> > Finally the implementation is done on the top creating nice diamonds in the
> > inheritance tree:
> > OsiCplex : public OsiLPSimplexPrimal,
> >            public OsiLPSimplexDual,
> >            public OsiLPSimplexBarrier;
> Something like this would still work with approach outlined above.
If the implementation is to inherit fornm the three OsiLPSimplexXXX classes
to have access to all method you have to decide between the three propositions below.

Another design is : 
1 - the abstract class class OsiLPSolve  (with the method solve).
2- three abstract classes 
class OsiLPSimplexPrimal : public OsiLPSolve
class OsiLPSimplexDual: public OsiLPSolve
class OsiLPSimplexBarrier: public OsiLPSolve
3- to instanciate the three classes according to the solver.
class OsiLPSimplexPrimalCplex : public OsiLPSimplexPrimal
class OsiLPSimplexDualCplex : public OsiLPSimplexPrimal
class OsiLPSimplexBarrierCplex : public OsiLPSimplexPrimal

The big disadvantage of this design is the implementation overhead due to the number
of classes to rewrite for each solver.

I see sevral advantage : 
1 - if in a method you want to have the possibility
to choose one method you just have to instaciate the right class.
For example : 
void SolveMyProblem(OsiLPSolve *lps);
You call this method with the choosen class (Primal, Dual, Barrier, etc).
SolveMyProblem(new OsiLPSimplexPrimalCplex(MyModel));
or 
SolveMyProblem(new OsiLPSimplexDualCplex(MyModel));

2- If you want to force to always use the given method you could force it 
using the type
void SolveMyProblemWithDual(OsiLPSimplexDual *lps)

3- No overhead due to test to know which method the user want to use.

4- the produced code is really smaller because only the classes (and thus
the code of method) used will incorporate in the object code.
If you only use the LPPrimalCplex all the code for the Dual will be not
included.



> 
> > The trouble comes when we want to do a solve() method, or getting the solution
> > or anything that is defined in multiple classes. If several parallel class
> > defines a solve method how will it be decided which solve is used? There are
> > three possibilities: 
> > 1) There should not be no name clashes, and call the mthods
> >    solveSimplexDual(), etc.
You have to think about all possible methods, if a new one appear you have to
add it in each classes.
With the design i propose you just have to add a class. You dont have to change
the actual interface of all the existing classes.

> > 2) We don't care about name clashes and if the solve method is invoked it has
> >    to be specified which one we want. E.g.:
> >       OsiLP* solver = new OsiCplex;
> >       /* at this point all we know about 'solver' is that it solves LPs */
> >       OsiLPBarrier* bsolver = dynamic_cast<OsiLPBarrier*>(solver);
> >       bsolver->OsiLPBarrier::solve()
> >       /* no we have selected to solve the LP with barrier */
> > Obviously 1) and 2) are sort of equivalent.
> > 3) Have a parameter that specifies from which class we want to pick a method
> > if it is ambiguous. This solution would effectively hide 1) or 2) from the
> > user. On the other hand this does require some coordination among totally
> > independent classes (or some serious juggling with typeid information). 
> > 
> > If these problems wouldn't be enough then we also have to consider
> > integerality, so there will be another pillar on the bottom: OsiInteger, which
> > contains nothing but integrality info on the data. Then we can have class
> > OsiMILP : public OsiLP, public OsiInteger;
> > etc. all rising to the top.
On more time, we need OsiVariable...
> > 
> > So, I'd like to solicit comments on this (e.g., did I remember correctly :-).
> > Once we come to a consensus how it should be done, I'll create a development
> > branch for Osi and would be very happy if someone would voluteer to make the
> > transition :-). If noone has the time now I'll do it eventually, but I doubt
> > I'll have time before sometime in December.
> 
> There also was a general proposition that we do try - catch around all
> methods in unitTest() for the OsiSolver, OsiSimplexSolver, etc. This would
> provide user with an info on what methods are really implemented right
> after Osi was compiled with a particular solver.
That could be also done but the problem here is the size of the code.
If I never use the Barrier method, my binary file will include it.
> 
> Best regards,
> Mikhail
> 
> > 
> > Cheers,
> > --Laci

Best regards
Bertrand Le cun-