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

[John J Forrest]

Mikhail Nediak asked some questions and I am answering on coin-contest.
The original questions and answers are at end of this note.


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

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

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

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

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.

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.