[Coin-osi-devel] Why Osi.branchAndBound()?

[Matthew Saltzman]

On Wed, 14 Mar 2007, Lou Hafer wrote:

> Folks,
>
> 	Ted and I have been exchanging a bit of email related to the discussion
> about OsiCbc, Osi.branchAndBound(), etc., and I thought I'd bring a piece of it
> back out to the list.
>
> 	Why does OSI include a branchAndBound() call?

Because we've always done it that way?

Seriously (from my memory as one involved in the early implementation 
stages, but post-design), a common use case that was envisioned for OSI 
was "cut and branch".  It was an experimental platform that would allow a 
user to load an LP and play with adding and deleting cuts and resolving.

It seemed like an obvious and easy thing to do to add the ability to 
"finish off" the solution process by calling the underlying solver's 
branch and bound routine.  All the initial solvers except Vol (we didn't 
have CLP/CBC at the time, we had OSL) were MIP solvers.  They all had a 
call that would take a solved LP and hot-start the B&B process with it.

>
> 	OSI (to my mind) is fundamentally oriented to continuous simplex
> optimisation. The definitions of the methods make that clear. Why add this one
> method  (branchAndBound) to handle MIP?  If MIP, why not NLP, or MINLP, or CLP
> (as in constraint logic programming)?
>
> 	There's just a basic wrongness to creating an OsiXXX object that calls
> OsiXXX.branchAndBound() that creates a CbcModel object that creates a new OsiXXX
> object (several, actually :-) and finally calls CbcModel.branchAndBound().

I agree that this is not particularly aesthetically pleasing.

But in a certain sense, linear continuous and linear discrete problems are 
not so different.  And OSI is overloaded, embodying as it does both 
instance mangement and solver management functions.

>
> 	If what we want is a `solve anything' class, then by all means let's
> make one. But let's not clutter it up with a bunch of methods that are specific
> to some particular problem class. And go top down. A `solve anything' solver
> should be capable of diagnosing the problem and farming it out to a more
> restricted solver class.
>
> 	OsiCbc, OsiSym, and OsiXXX.branchAndBound() make little sense to me as
> solvers for MIP problems. Sort of like trying to use a Blackberry while wearing
> boxing gloves.
>
> 	Going the other way, it is possible to write a good, efficient
> branch-and-cut code that's agnostic about the underlying LP solver.  And can use
> other types of solvers where appropriate.

Isn't that the original motivation for CBC?

The discussion was motivated by the question: If I can solve MIPs with 
OsiCpx and OsiXpr, wouldn't it be nice to be able to solve MIPs with 
OsiClp?  John's answer was to throw together SBB, which later grew and 
morphed into CBC.

>
> 	So, let's hear it --- why do we need this method at all? And if we do
> need it, why does it belong in OsiSolverInterface?

Well, people seem to want it.  (Don't laugh--legacy support is not to be 
trivialized.  Look at the burden Microsoft bears.)

Now, I think most people would understand that not every solver lends 
itself to supporting B&B (c.f. Vol).  But if you want to engage in 
cut-and-branch and you want an end-to-end open-source solution, and you 
want the portability of OSI, you can't get it the way things are built 
now.  You can engage CLP through OSI, but you can't finish off a MIP 
with it.  You can solve MIPs with CBC, but you can't get it through OSI. 
That at least appears to undermine our commitment to either portability or 
open source.

I'm focusing on the core suite (OSI/CGL/CLP/CBC/VOL) here.  I think 
SYMPHONY and BCP complicate the discussion a bit.  But the point of 
OsiCbc, OsiSym, and in fact any OsiMipSolverThatNeedsAnLpEngine, is 
largely to take advantage of portability in the handling of model 
instances, not necessarily to provide fine control of the MIP process (as 
opposed to the LP process).

-- 
 		Matthew Saltzman

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