adventures in optimization

The charming adventures of an analyst and his solver.

« Friday, January 13, 2012 »

Normal Magic Squares

An integer programming formulation of the normal magic squares problem.

As a followup to yesterday's post, I created another python-zibopt example for finding Normal Magic Squares. This is similar to the Sudoku example, except that here the number of binary variables depends on the square size. In the case of Sudoku, each cell has 9 binary variables -- one for each potential value it might take. For a normal magic square, there are $n^2$ possible values for each cell, $n^2$ cells, and one variable representing the row, column, and diagonal sums. This makes a total of $n^4$ binary variables and one continuous variables in the model.

However, there are no big-Ms.

I think the neat part of this code is in lines 57-62. It creates sums of the $n^2$ variables for each cell with their appropriate coefficients (1 to n^2) and stores those expressions to make the subsequent constraint creation simpler (try doing that in your modeling language!). All made possible thanks to python-algebraic.