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

[Irv Lustig]

John Forrest wrote:

> I wanted to see if I could implement a Constraint Programming
> idea such as "All Different" into Cbc; also I had been asked
> to make sure N-way branching worked.  Finally Irv Lustig had
> asked - "What can you do with Cbc that you can't do with
> Cplex?".  On the way back from INFORMS I was sitting next to
> a person solving Su Doku puzzles and I thought - can you
> write a Su Doku solver with Cplex?

Yes.  The IP formulation is trivial.  And generally the CPLEX presolve
solves the problem without requiring the root LP to be solved.  I had
one case where the root LP needed to be solved, and then the root LP had
an integer solution.

> 
> I have implemented CbcBranchAllDifferent which stops two
> general integer variables being the same by imposing two
> branches x <= y-1 and x >= y+1.
> Obviously users can modify this to obtain their own cut
> branch rules.  I have also put in a CglAllDifferent cut
> generator which fixes variables based on the above logic.  I
> may improve the speed of this later.

Note that you could implement the above using what are known as "goals"
in CPLEX.

Brady Hunsaker wrote:

> Right now a first-year grad student in my linear optimization
> class is investigating solving Sudoku puzzles using just an
> IP formulation.  I thought that constraint programming ideas
> like you mention would be better, but to my surprise he said
> his formulation can quickly solve the largest puzzles he can
> get his hands on.  I haven't looked at any details yet.  I'll
> let you know what he did and whether his early report is accurate.

The CP formulation works just as well, without requiring any search to
solve the puzzles.  

> 
> In response to the comparison of CPLEX and CBC, my sense is
> that it doesn't make much sense to compete on features.  CBC
> will naturally have some cutting-edge features (like the
> all-different constraints) sooner than CPLEX, because a
> larger group of people can experiment and add them.  But if
> they prove useful, then CPLEX will quickly add them.
> 
> In my opinion, the answer to the question "What can you do
> with CBC that you can't with CPLEX?" is
> - you can download it for free and use it at full strength on
> as many computers/processors as you want
> - you can share it with your friends and coworkers
> - you can experiment with new features like the all-different
> constraint or pay whomever you like to experiment for you
> 
> I see CPLEX as serving a different need (for now) then CBC.
> I don't think we should make the mistake of thinking that we
> are competing with CPLEX, especially not on their terms
> (speed, stability, features).  In my mind the question was
> designed to frame the comparison that way, when
>   in fact the primary advantages of CBC are different.  Of
> course, I think that over time, the open-source model will
> allow CBC to have more features and stability.

You misunderstood the question.

Leaving aside the free-versus-pay argument (because that is more a
"religious" discussion than anything else), my question was whether
there was a *feature* of the basic COIN solvers that was not in CPLEX.

I claim that any branching strategy, cut generation strategy, etc.,
could be implemented using CPLEX.  An example is the all-different
strategy that John Forrest implemented.  You could do that with CPLEX as
well, as I mentioned above.

About the only thing that a COIN solver can do that CPLEX can't is that
you can implement branch-and-price with things like SYMPHONY.

So, let's suppose you have a cut generation strategy, and you implement
it using the CGL.  Or you have a branching strategy, and you implement
it on top of CBC.  You could also implement that same strategy using
CPLEX, and publish the cut using the CPLEX API's, and be able to share
the code just like you do with COIN.

Please let's not get into a discussion of open source versus commerical
software.  That's not what the issue is.  I'm asking whether there are
things that you need to do as a researcher with COIN that are not
possible with CPLEX.  That was the question that I posed.

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