[coin-discuss] expanding Osi -- ideas sought

[Marc Pfetsch]

Hello all,

here's an idea, refering to what Laci proposed for the design of
the OSI interface (see below).

Maybe it's not a bad idea to have an intermediate level between the raw
Osi-class and the implementations for specific solvers, which
distinguishes different solution strageties like simplex-methods, interior
point methods, and the volume algorithm. This would then solve the warm
start issue, since for simplex methods it's clear what has to be stored,
while for "pure" infeasible interior point methods it could be a point (an
interior point method with crossover could then behave like a simplex
method).
   
It's also clearer for the user what to expect from the outcome (if you
want to be fast, you have to think about it anyway). It also makes the
other raised issues simpler - as far as I see, problems arise where one
wants to have common data structures for all methods.

Well, I acknowledge that this is just the idea of Osi, but in my opinion
one really should make the general class just as general as there are no
performance penalties, e.g. the construction of the problems are similar
to all methods and if the user just wants to solve an LP or two, it may
not matter how special things like warm- starts are handled.

Does that make sense?
Any better ideas?


Marc




On Tue, 14 Nov 2000, Laszlo Ladanyi wrote:

> At the San Antonio INFORMS meeting a couple of core team members got together
> and discussed how to expand the OSI, more precisely the OsiSolverInterface
> class. This time our primary aim was to provide the functionality necessary
> for writing a high quality branch and cut code (in other words, make it
> possible for Bcp to use Osi). The issues listed below came up. I'd like to
> encourage everyone to share their thoughts on any/all of these questions. I
> (as the primary maintainer of Bcp) would like to make the transition as soon
> as possible, so people with other licenses than OSL could use Bcp.
> 
> I'd like to start coding next week, so if you have ideas, please post them
> this week. Thanks!
> 
> Even though this post is fairly long, there are a couple if interesting design
> issues that we'd like to get as much input as possible. Please, read it
> through.
> 
> --Laci
>   ladanyi at us.ibm.com
> 
> -----
> 
> 1) Termination code
> 
>    At the moment none of the solve methods of Osi return a termination code.
>    A minimal set of termination codes we thought necessary are listed below.
>    Some solvers provide more information (e.g., the infeasibility was detected
>    in the presolving phase), but we really think these are enough to start
>    with, and other codes can be added later as the necessity arises.
> enum OsiTermcode {
>    /// The algorithm was not executed (see later exact/approximate algorithms)
>    OsiNotExecuted = -2,
>    /// The optimization was abandoned (due to, e.g., numerical difficulties)
>    OsiAbandoned    = -1,
>    /// Optimal solution is found
>    OsiOptimal      = 0,
>    /// Primal infesibility detected
>    OsiPrimalInf    = 1,
>    /// Primal unboundedness is detected
>    OsiPrimalUnb    = 2,
>    /// Primal infesibility detected
>    OsiDualInf    = 3,
>    /// Primal unboundedness is detected
>    OsiDualUnb    = 4,
>    /// Iteration limit is reached
>    OsiItlim        = 5,
>    /// Objective limit is reached
>    OsiObjlim   = 6
> };
> 
> 2) Parameters 
> 
>    Most solvers can behave very differently if various parameters are set
>    differently. So how to set parameters? There are a few that all solvers
>    should be able to interpret (like objective limit, time limit, iteration
>    limit, though this latter one is interpreted very differently for a simplex
>    based method and for the volume algorithm), but there are quite a few
>    parameters that are solver specific. How to handle those? One possibility
>    is when someone wants to set a parameter he should do a dynamic cast of the
>    OsiSolverInterface object to each OsiXxxSolverInterface and set the
>    appropriate parameter for the Xxx solver. This is rather cumbersome.
>    We'll take a look at how gams, ampl handle this but any input would be
>    appreciated. 
> 
> 3) WarmStarting
> 
>    What is warmstarting? Essentially, it is some sort of an information that
>    the solver can use to speed up optimization. It can be, e.g., an advanced
>    basis, a primal/dual vector pair, etc. In general, warmstarting info should
>    be possible to put together by the user, but also, the solver should be
>    able to provide warmstarting info for later restart. Thus the following
>    suggestion came up:
>    - Have an OsiSolverWarmStart abstract base class with no members at all. 
>    - Derive all warmstart type from that. Possible warmstart infos that we
>      were able to come up include: basis status of each variable and/or row,
>      primal and/or dual vector. If a warmstart info is general enough (not
>      solver specific) then it should be defined as, e.g., 
>       OsiWarmStartPrimalDual, so each solver could use the same warmstart info.
>    - Have an `OsiSolverWarmStart* getWarmStart()' method in OsiSolverInterface
>      This method should return any sort of warmstart the solver wants.
>    - Have a `int setWarmStart(OsiSolverWarmStart*) method. In this method the
>      solver should try to dynamic cast the argument into each type of
>      warmstart it can interpret, and if a cast succeeds then prepare for
>      warmstart and return 0, otherwise return -1. Note that being able or not
>      able to set warmstarting info should not influence succesful optimization
>      later on (apart from speed and possible numerical difficulties...).
>    - Maybe overload setWarmStart()? This would have the advantage the just
>      from the class description it would be immediately obvious what sort of
>      warmstart infos are defined in general.
> 
> 4) HotStarting
>   
>    The difference between hotstarts and warmstarts is that info on the latter
>    should be possible to store, modify and restore by the user, while saving
>    and restoring hotstart info should be possible only by the solver. The
>    reason to make a distinction between warm- and hotstarts is efficiency.
>    When warmstart information is loaded into a solver, most likely some
>    precomputation has to be done (like factorization for a simplex based LP
>    solver). Hotstarts may avoid that penalty.
> 
>    The primary use of hotstarts would be in strong branching. When strong
>    branching starts, a hotstart info is saved and from that hotstart info the
>    problem is resolved over and over again with only bound changes (but no
>    changes to the matrix) between two resolving. Proposed method names:
>    saveHotStart() or markHotStart() 
>       to mark the snapshot where subsequent reoptimizations will start from, 
>    hotStartSolve() resolve from the hotstart 
>    umarkHotStart() to indicate to the solver that it can forget the hotstart
>       info. Maybe this method is not necessary? Forget the info only if a new
>       mark request is made or when the matrix changes?
> 
> 5) Dealing with infeasibility
> 
>    In a branch and price method one may want to generate columns to restore
>    feasibility when infeasibility is detected. This means that one wants to
>    find columns that in some sense "cut off" dual rays. Ideally, one would
>    want to have access to the full dual cone that proves primal infeasibility,
>    so the method we propose is 
>    std::vector<double*> dualRays();
>       This method should return a vector of arrays, each of which is a dual
>       ray. At least one ray must be returned, but there can be more. 
>    For the sake of symmetry there should be an
>    std::vector<double*> primalRays();
>       which return a vector of primal rays proving dual infeasibility.
> 
> 6) Approximate vs. exact solutions
> 
>    For branch and bound all we need is a lower bound (supposing minimization).
>    For cutting planes all we need is a point in space that need to be
>    separated. Therefore most of the time we would be OK with an approximate
>    primal solution and a lower bound on the LP value. It is quite possible
>    that a solver can provide only exact (simplex -- forget about tolerances
>    for now...) or only approximate solution (volume algorithm or interior
>    point code terminating early) or both solutions (volume followed by a
>    simplex crossover). Since approx solutions are usually much faster and most
>    of the time sufficient, it's reasonable to design Osi so that a single call
>    to optimization can deliver either/both solutions. What is the right
>    design? 
>    
>    For querying the solutions have three methods for every type of query:
>        colsolApprox(), colsolExact(), colsol()
>    the first two are obvious, the last returning the exact colsol if an
>    exact algorithm was executed, the approx solution otherwise. Note that
>    this is the place where the OsiNotExecuted termination code will play a
>    role.
> 
>    As for which type of algorithm is executed, two proposals came up in our
>    discussion: 
>    a) Make two separate function calls to all solve type methods: solveExact()
>       and solveApprox().
>    b) The sole type methods should have an argument indicating whether exact
>       or aproximate solution is *preferred*. Preferred, because the solver may
>       not be able to deliver the one or the other. Then the solver would do
>       whatever it wants, and termcodeExact and termcodeApprox would have to be
>       examined to find out what has happened.
> 
> 
> 7) Manipulating the matrix and the rim vectors
> 
>    There need to be much more methods... like adding columns, rows (not just
>    through applyCuts()), deleting columns, rows, etc.
> 
> 8) What should happen when a formulation is no longer needed?
> 
>    E.g., when fathoming a node. The clean solution is, of course, to delete
>    the OsiSolverInterface instance and create a new one when the new search
>    tree node is processed. It is very nice but it comes with a performance
>    penalty; it might take lots of time to clean out and delete the object.
>    Also, it might be advantageous to delete only the problem instance, but
>    keep all the parameters, user hooks (if there are any).
>    The same question comes up if loadProblem() is invoked for an
>    OsiSolverInterface object that already has a problem loaded. Should the old
>    problem be deleted and replaced with the new (I'd say yes)? Should the
>    parameters and similar things reset (I don't know)?
>    Maybe the best solution is to have an unloadProblem() method which deletes
>    just the problem formulation so a new one cen be loaded in, and a clean()
>    method that restores a pristine state?
> 
> -------
> 
> That's all for now... Feel free to reply any (all?!) questions posed here.
> And remember, every vote counts :-).
> 
> 
> 
> ----
> To get off the coin-discuss list, send a message containing the word
> "unsubscribe" (in the body, not the subject) to
> <coin-discuss-Request at oss.software.ibm.com>.
> 
> Send Majordomo commands to: <coin-discuss-Request at oss.software.ibm.com>
> To contact a human:         <coin-discuss-Owner at oss.software.ibm.com>
> To post to the list:        <coin-discuss at oss.software.ibm.com>
> 



----
To get off the coin-discuss list, send a message containing the word
"unsubscribe" (in the body, not the subject) to
<coin-discuss-Request at oss.software.ibm.com>.

Send Majordomo commands to: <coin-discuss-Request at oss.software.ibm.com>
To contact a human:         <coin-discuss-Owner at oss.software.ibm.com>
To post to the list:        <coin-discuss at oss.software.ibm.com>