[Coin-lpsolver] Re: New branching ideas for CBC

[Irv Lustig]

Jean-Sebastien Roy <js at jeannot.org> wrote:
> 
> A very small point: for example, as far as I know, using CLP
> you can extract a ray without disabling the presolve (which
> may be required when using CPLEX).

If by "extract a ray", you mean obtain the extreme ray that proves a
problem is unbounded, that is available with CPLEX.  You're correct that
you'd have to turn off presolve, because we don't "unpresolve" the
extreme ray.  I think this could be done.  I'll pass it on to our R&D
team.

> 
> PS: On a side note, as a researcher open source vs commercial
> *is* very much an issue: for example, I cannot run CPLEX on
> the systems I use for research (Mac OS X and FreeBSD).
> 

That's a fair comment!  And since I have Macs in my house for personal
use, I certainly can sympathize with you on this one.

> 
> Although it's true that I can share code that uses CPLEX's
> API, the only people that can take immediate advantage of it
> are people who also have a CPLEX license.  These are also the
> only people who can easily build on my ideas and share their
> new ideas.  Matt has just made this point.

Well, you all know that the community of people with CPLEX licenses is
quite large, so that restriction shouldn't be such a big one for you.  

> 
> In addition, there are some fundamental changes that are
> awkward or impossible to implement using any API.  For
> example, I am currently looking at estimating time to finish
> a branch-and-bound process.
> Cornuejols, Karamanov, and Li recently looked at this problem
> using CPLEX.  One of the authors told me that they parsed the
> CPLEX log file in order to find out the structure of the tree
> for their estimates.
> Whether or not parsing the log file was necessary, it was not
> obvious to them whether there was an easier way.  By
> experimenting with open-source solvers, I have much easier
> acess to more information.  I have more hope of a good
> outcome and spend less time with coding contortions.

But that information *is* available, for CPLEX and I bet it is available
for XPRESS as well.  You just have to ask.  Or search the 1785 pages of
CPLEX reference manual documentation.  And I'm betting that you'd spend
less time working with a well documented API than you would combing
through the non-documented open source code of CBC.

I'm not against open source code.  And I do think that COIN serves some
useful purposes, and if I was still an academic, I'd probably be a
contributor!  But I still maintain that anything that you can do with
CBC or CLP, you can do with CPLEX.  Maybe it isn't obvious from the
CPLEX documentation, but if you just ask our tech support folks, they
will point you in the right direction.  And if there isn't something
that CPLEX can do, the only way we'll consider doing it is if someone
takes the time to make a request for a new feature.  Besides, if what
you want to do is there, then there is a support mechanism, consisting
of many people, that are there to make sure that the product can do what
it says it can do.

Just to give you a bit of historical perspective, about 10 years ago, it
was impossible to write your own branching strategy with CPLEX.  We used
to tell people "Get MINTO".  At some point, we created the API's that
allowed people to create those strategies, because we saw the customer
demand (primarily in academia) for that feature.  This process is a
major way that any team creating commercial software adds features -
they find out the needs from their customers.  Now, as John Forrest
pointed out in San Francisco, we won't implement it as fast as in an
open source effort.  But after being in this business for over 17 years,
we've assembled a lot of knowledge about the needs of the community and
have spent many person-years implementing features that hardly ever get
used.  I'd love to see people write papers testing new branching
strategies, cutting planes, heuristics, etc., on top of our API's, so
they can demonstrate whether their ideas work as compared to a well
implemented commercial solver.  

By the way, while I clearly have an interest in promoting CPLEX, I'm
pretty sure that my colleagues over at Dash would be willing to
substitute "XPRESS-MP" for "CPLEX" in the above comments, and I'm sure
they are interested in the question "What can you do with CBC or CLP
that you can't do with XPRESS-MP?"

        -Irv Lustig, PhD
         ilustig at ilog.com       
         Manager, Technical Services, 
         Optimization and Visualization 
         ILOG, Inc.
         http://www.ilog.com/