The magic square as a benchmark: comparing manual solution with MIP solution and AI algorithm and improved evolutionary algorithm
José Barahona da Fonseca · 2005
I found the magic square a simple problem with a very rich combinatorics: there are (n2)! manners to fill the n×n matrix with integers between 1 and n2, without repetitions, but only very few of them are magic square [1]. For n=4, generating all the 16! permutations, I found 7040 magic squares and 549504 relaxed magic squares. In the literature many people believe that the number of magic squares of order four is 880, but in fact these are the canonical magic squares from which can be generated all the other by rotation and transposition or reflection. So I use the magic square as a benchmark to compare mathematical programming, namely mixed integer programming (MIP), with Genetic Algorithms (GAs), that I will show are much more powerful to solve these kind of discrete combinatorial explosive problems. Then I got the idea to compare GAs with the human being, and I developed a prototypes of a game where the objective was to get the relaxed magic square in a minimum number of changes between two elements of the matrix. This game could be used for management training since in management problems we often have a limited budget, a lot of constraints and objectives to reach that could be formulated in a similar matrix form. Finally I developed an artificial intelligence minimax algorithm that imitates a human solving the magic square and show that in most cases its performance, in terms of number permutations, is better than the performance of the GA algorithm.