[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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 */