Sunday, October 19, 2008

Magic Squares with MS CSP solver

This model generates Magic Squares (http://en.wikipedia.org/wiki/Magic_square) using the Microsoft Solver Foundation Excel tool.

As we have no objective, this can be formulated as a constraint programming problem. This makes it easy to use the alldifferent constraint (using the unequal construct in OML).




This remains a difficult problem: only quick solutions up to N=5.



Update: I tightened the symmetry breaking constraints and used a different CP heuristic (Domain over Weighted Degree). Choosing the correct heuristic was not done by deep insight but rather trial-and-error. This allowed me to solve even up to N=10 quickly.




It will be difficult to get good performance from a MIP solver on this. The MIP formulations for the all-different constraint are very demanding for a MIP solver. See e.g. H.P.Williams, Hong Yan, "Representations of the all-different Predicate of Constraint Satisfaction in Integer Programming," INFORMS Journal on Computing, Vol. 13 (2001) 96-103,
http://www.lse.ac.uk/collections/operationalResearch/pdf/PWilliams_2001_IJOC.pdf.

4 comments:

  1. That's interesting. Would it be possible to publish the computational time requirements for some values of N?

    Did you try the algorithm with tougher problems such as the knight's Tour?

    ReplyDelete
  2. This is beta software, so it may be better to wait doing any type of timings until the final is out (in november).

    I have not implemented the Knights' Tour. But as the preview can be downloaded for free from http://code.msdn.microsoft.com/solverfoundation, you should be able to implement this yourself.

    ReplyDelete
  3. Hi did you look into programming the Knights Tour in solver foundation? I am very interested.

    Thanks.

    Ravi

    ReplyDelete
  4. No I have not looked into that, but I am always available for contract work :).

    ReplyDelete