[Coin-lpsolver] New branching ideas for Cbc

[John J Forrest]

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!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20051124/415fc373/attachment.html>