[Coin-lpsolver] New branching ideas for Cbc

[Brady Hunsaker]

John J Forrest wrote:
> 
> One reason for going to Cbc version 1.00 was to imply a more measured 
> set of changes.  One exception I made was that of adding new branching 
> classes etc.
> 
> 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?
> 
> If you live in the UK you must know what a Su Doku puzzle is, for some 
> others - for a 9 x 9 Su Doku puzzle you fill it in using numbers 1 to 9 
> and each row and column must be all different as must the obvious 3x3 
> squares.
> 
> 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.
> 
> I found that this was not sufficient to do well at the Independent super 
> Su Doku puzzles (16x16) for which there is a prize.  This is because 
> general integer variables at a bound are not enough for the logical 
> fixing.  So I have implemented N way branching so that we can fix the 
> general integer variables more easily.  And while I was at it I added a 
> trivial CglStored cut class where the user can put any cuts and then 
> have them added in if they are violated and the obvious AllDifferent row 
> cuts could go there.  To see more look at the sudoku.cpp example in 
> Cbc/Samples.  There is also a simple nway.cpp example.
> 
> John Forrest
> 
> PS I am sure it is cheating to use this to win prizes!
> 

I think the all-different constraint could be quite useful in a variety 
of settings.

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.

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.

Brady