Wednesday, February 9, 2011

Again Sudokus

I had to give a presentation about a proposal to implement a large and complex scheduling application using mathematical programming or constraint programming. Of course the audience had never heard about math programming, LP,MIP or CP. This make you realize again how small and specialized this field is, out of sight of “normal” people.

Of course I always show my Sudoku example:



A good MIP solver solves this in zero nodes: the presolver will take care of it completely. E.g. for the 81 x 81 problem below I see:

Starting Gurobi...
Optimize a model with 26244 Rows, 531441 Columns and 2125764 NonZeros
Presolve removed 26244 rows and 531441 columns
Presolve time: 1.67s

Model and data files:
Btw. this is how an 81 x 81 problem looks like:



Now if these solvers would just be as fast on my real models….

2 comments:

  1. It's 'Sudokus' (plural) not 'Sudoku's' (possessive.)

    ReplyDelete
  2. Very nice Erwin.

    I'm fast at Sudoku solving and teach others to be fast, but that my friend is sweet!

    ~ Bill W.

    ReplyDelete