[Coin-discuss] Glpk Osi for interior point?

[Matthew Saltzman]

On Mon, 2008-02-04 at 22:10 -0500, Brady Hunsaker wrote:
> The simplex and interior-point solvers in GLPK are fundamentally 
> separate solvers.  It isn't natural to try to put both of these in one 
> OSI interface.  Therefore, I think that Stefan's suggestion of a 
> separate interface for GLPK's interior-point solver is the right 
> approach, if someone wants it badly enough to write the interface.

I'd entertain a proposal for a solver interface-specific IP extension as
a model for a universal design.  That would at least give us a starting
point to discuss building in the necessary base-class methods and data.

Parameter setting is probably the most difficult/annoying aspect of this
problem.

I'd extend the OsiGlpk class with separate calls to invoke the IP solver
and get the IP solution.  The algorithms and solution characteristics
are different enough that it may be difficult to blend them into the
existing simplex structure.  It will almost certainly be simpler to
avoid the issue altogether.

> 
> Last time I checked carefully, GLPK did not have a cross-over routine to 
> convert a solution from the interior-point routine into a basic optimal 
> solution.  I expect that is still true.

Whether that's a show-stopper depends on the application, of course. 

The easiest thing to do for yourself is take the primal and dual
solutions and try to construct a basis based on complementary slackness,
then start the simplex method with it.  If you guess wrong, it will cost
you, but with luck not too much more than a real crossover and with
total IP plus crossover cost less than all-simplex.

If it turns out the constructed basis is neither primal nor dual
feasible, there are ways to recover that can be implemented fairly
easily.  They don't make for guaranteed crossover performance, but they
should work OK.

> 
> Brady
> 
> Stefan Vigerske wrote:
> > Hi,
> > 
> >> Am I correct in observing that there is no way of using the GLPK's 
> >> interior-point solver via OSI? 
> > 
> > Yes, no way yet.
> > 
> >> And if so, is there any plan to add this 
> >> feature? I have a case where the interior point is at least 50x faster 
> >> than simplex, so it would help...
> > 
> > Actually trying GLPKs interior point solver is also on my TODO list, and 
> > getting it into OsiGlpk would be nice.
> > I have not had a look at it and how much different its use is from glpks 
> > simplex method.
> > 
> > However, since there is nothing interior point related in the Osi base 
> > class, it would be some OsiGlpk specific extension, and the question is 
> > how to do this nicely.
> > Should there be a method similar to initialSolve() that calls the 
> > interior point solver? Or should there be a (OsiGlpk-specific) parameter 
> > that says that the interior point solver should be used, so the next 
> > time when initialSolve() or resolve() is called, then this parameter is 
> > checked and the appropriate method called?
> > 
> >> I can, of course, call the lpx_interior method directly, but then the 
> >> Osi still does not know about the solution, since all the access 
> >> functions (status, objective function and column values) are different 
> >> when using lpx_interior...
> > 
> > This sounds somehow bad. That would mean that every method in OsiGlpk 
> > which accesses the glpk-solver needs to check whether the last solve was 
> > an interior point solve or a simplex solve, and then call the 
> > corresponding glpk function.
> > Might be better to have a OsiGlpkInterior interface?
> > 
> >> It would thus help a lot if I could use the interior-point solution as a 
> >> starting point for the standard simplex solver. Is this possible? (I 
> >> tried setColSolution, but it does not seem to have any effect at all.)
> > 
> > Is there a GLPK option that tells the interior point solver to 
> > automatically do a crossover to the simplex method? (maybe I should 
> > check the manual...)
> > 
> > Best,
> > Stefan
> > 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
-- 
                Matthew Saltzman

Clemson University Mathematical Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs