[Coin-contest] Wish list for OsiClp, questions on Sbb

[Mikhail Nediak]

> >I guess, there are really two types of issues that I care about. First
> >group is Osi/Clp. Ideally, I would like to have an extended
> >Osi interface to Clp (it is that OsiSimplexInterface that I and
> >Jonathan posted on coin-discuss a few month ago). In this case we could
> >test our complete pivot-based heuristic with all bells and whistles.
> >Osi way makes the heuristic implementation more general, since it would
> >work with any solver that supports the extended interface. For now, we had
> >this interface for CPLEX 7.x and Bob Vanderbei's SIMPO. Of course, I
> >would implement all these methods (or at least the most important ones)
> >myself, if I only had some guidance on how to approach this  task. I am
> >attaching the interface's header to show what kind of methods
> >we had in mind. Most of these are perfectly implementable for CPLEX using
> >standard functions or the ones described in CPLEX's "Advanced Reference
> >Manual" (read "potentially non-portable to future versions" :-( )
>
> Mikhail - I will try an add some code to the OsiClpSolverInterface for
> OsiSimplexInterface.  I am tempted to include it in OsiSolverInterface base
> class and have the default be to abort if a function is called.  That way
> you could easily get Cplex and Clp to work.  It may take some time before I
> get round to it but it should be in by end of February.

I think it may be even better to have an interface class for a particular
solver inherit from OsiSimplexInterface (which is purely virtual just like
Java interfaces). In this case, one can do run-time checks whether it is
actually supported using a pointer to OsiSolverInterface, e.g.

OsiSolverInterface* sol = ...;
...
OsiSimplexInterface* simplexSol = dynamic_cast<OsiSimplexInterface*>(sol);
if (simplexSol == NULL) {
//...
} else ...

This will allow for a greater programming flesibility (and this is how we
did it with CPLEX anyway).

>
> >On the other hand, if implementation of this extension is too tedious
> >and/or requires some serious modifications to Clp, we would even be
> >satisfied with regular Osi interface functionality. We could then test a
> >much simplified version of the heuristic. I would still care, however, if
> >it is possible to easily extract tableau info from Clp (in this case we
> >could also add and test some extra Cgl-style cut generators).
>
> If I do the above, the tableau information will be easily available.  At
> present it can be extracted when using any solver by using
> CoinFactorization.  To see how look at CglGomory.cpp and lines with ==== in
> them (just checked in).

OK

> >In both cases, there are still some Sbb issues. For example, how often
> >are heuristics called in Sbb? From our experience, we had to look at the
> >gap of the current subproblem and its integrality relative to other
> >subproblems in the pool to save some time. Otherwise, too much effort is
> >wasted.
>
> This is an area which needs a lot of work.  At present it is very crude.
> The user can say do every k nodes or if -1 then it checks every 100 nodes
> if any cuts are generated - anyway that's approximately what happens.

OK. Then I may try to improve on it.

> >Second, what does the solver_ in the model of SbbHeuristic object
> >correspond to? Can I make sure that when a heuristic is called, it
> >contains the current subproblem with relaxation solved to optimality
> >(i.e., proper LP basis loaded)? Will all applicable cuts be "in"?
> >Third, will I be able to use some cut generators inside the heuristic (it
> >is really a heuristic branch-and-cut)?
>
> In SbbHeuristic model_->solver() gives the OsiSolverInterface pointer to
> current model (with cuts and optimal).  The underlying solver will be same
> one set in main program.  model_->continuousSolver() should give model with
> initial state.

This is perfect -- exactly what we need.

> At present you can use cut generators in the heuristic but there is no way
> to pass these cuts back.  If you were going to then the code should really
> be in as a cut generator?  If you are going to modify model then clone the
> solver and modify that.

It may prove difficult in the most general version of the heuristic, since
cuts are generated using by-products of heuristic run.

Thanks a lot for the advice.

Best,
Mikhail Nediak

>
> Please keep the questions coming.
>
> John Forrest
>
> --------------------------------------------
> > Mikhail,
> >
> > Sbb uses the Osi interface.  I am at present working on a first version
> of
> > an integer presolve, which for the moment assumes that the user is
> actually
> > using clp as the solver.  So I do a dynamic cast to clp and then use
> Clp's
> > presolve.  I intend to enhance that presolve and also give it an osi
> > interface.
> >
> > However I think it valid to allow the casting to clp and then using clp
> > interface so my question to you is - do you want to do things at the Osi
> > level or Clp level.  If at the Clp level I have more freedom.
> >
> > If it is at Clp level, what exactly do you want?  For primal pivot in
> > choice or dual pivot out choice it is easy - for primal look at
> > ClpPrimalColumnPivot.hpp and ClpPrimalColumnDantzig.?pp (as that is
> > simplest).  The corresponding pivot out/pivot in is more problematic but
> > anything can be done.
> >
> > So give me a hint.  Also if you think your requests are of sufficient
> > generality, indicate that and I can post replies to coin-lpsolver and/or
> > coin-contest.
> >
> > John Forrest
> >
> >
>
>
>
>
> The original note from Mikhail.
>
> I am trying to test certain pivot-based heuristic with Sbb and the current
> interface does not seem sufficient. So I will have to, most likely, modify
> the place in the Sbb code where it is called (and, also the manner and
> the frequency of the calls). Could you please give me some suggestions on
> where I should start? Any advice is greatly appreciated.
>
> _______________________________________________
> Coin-contest mailing list
> Coin-contest at www-124.ibm.com
> http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-contest
>