[coin-discuss] expanding Osi -- ideas sought

[Laszlo Ladanyi]

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>