help-glpk
[Top][All Lists]

## Re: [Help-glpk] magic square/jssp

 From: Andrew Makhorin Subject: Re: [Help-glpk] magic square/jssp Date: Sat, 3 Feb 2007 20:42:43 +0300

```> 1. I am writing  now a magic square program in math prog.I have a problem
> with formulating a constraint, that all the values in the square must be
> different.

There are many ways to formulate that puzzle as mip. You encounter
a trouble due to an inappropriate choice of binary variables.

Below here is an example, where x[i,j,k] = 1 means that cell [i,j] is
assigned number k.

------------------------------------------------------------------------

/* magic.mod */

param n, integer, > 0, default 3;

var x{i in 1..n, j in 1..n, k in 1..n^2}, binary;

var s;

var p1{1..n}, >= 0;
var p2{1..n}, >= 0;
var q1{1..n}, >= 0;
var q2{1..n}, >= 0;
var r1, >= 0;
var r2, >= 0;
var s1, >= 0;
var s2, >= 0;

s.t. aaa{i in 1..n, j in 1..n}: sum{k in 1..n^2} x[i,j,k] = 1;
s.t. bbb{k in 1..n^2}: sum{i in 1..n, j in 1..n} x[i,j,k] = 1;
s.t. ccc{i in 1..n}: sum{j in 1..n, k in 1..n^2} k * x[i,j,k] = s+p1[i]-p2[i];
s.t. ddd{j in 1..n}: sum{i in 1..n, k in 1..n^2} k * x[i,j,k] = s+q1[j]-q2[j];
s.t. eee: sum{i in 1..n, k in 1..n^2} k * x[i,i,k] = s+r1-r2;
s.t. fff: sum{i in 1..n, k in 1..n^2} k * x[i,n-i+1,k] = s+s1-s2;

minimize z: sum{i in 1..n} (p1[i] + p2[i] + q1[i] + q2[i]) +r1+r2+s1+s2;

solve;

printf "s = %d\n", s;

for { i in 1..n }
{   printf { j in 1..n } "%3d", sum{k in 1..n^2} k * x[i,j,k];
printf "\n";
}

/* eof */

```