MIP for puzzle

[pelicano...@gmail.com]

Hello!

I try to describe problem http://www.primepuzzles.net/puzzles/puzz_835.htm for N=3.

I am doing so



param n integer, := 3;
set Z := {3,5,7,11,13,17,19,23};

var X {1..n, 1..n} integer in Z;
var S1 {i in 1..6} = X[2 - i mod 2, 3 - i mod 3] + X[2 - i mod 2 + 1, 3 - i mod 3];
var S2 {i in 1..6} = X[3 - i mod 3, 2 - i mod 2] + X[3 - i mod 3, 2 - i mod 2 + 1];
var S {i in 1..12} = if i<=6 then S1[i] else S2[i-6];

subject to st: alldiff {i in 1..12} S[i];


option solver jacop;
option jacop_options 'version timing=1 outlev=1 outfreq=10 timelimit=60';

#option solver gecode;
#option gecode_options 'outlev=1 outfreq=10 timelimit=60';

#option solver ilogcp;
#option ilogcp_options 'version timing=1 timelimit=30 logperiod=1000000 outlev=verbose';

solve;
display X;
display S;



Please tell me, why I get "infeasible problem"?


[Robert Fourer]

In general the message "infeasible problem" indicates that there is no way to assign values to the variables that will satisfy the constraints. For your particular model this means there is no way to assign values from {3,5,7,11,13,17,19,23} to the X-variables so that all 12 values of S[i] are different.

To check that the expressions for S1 and S2 are having the desired result, you can use the command "expand {i in 1.._ncons} _con[i];".

If you know of a feasible solution that the solver isn't finding, then please post a copy of the solution so that we can investigate this further.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of pelicano...@gmail.com
Sent: Wednesday, June 29, 2016 2:07 PM
To: AMPL Modeling Language
Subject: [AMPL 12248] MIP for puzzle

I try to describe problem http://www.primepuzzles.net/puzzles/puzz_835.htm for N=3.

I am doing so
param n integer, := 3;
set Z := {3,5,7,11,13,17,19,23};

var X {1..n, 1..n} integer in Z;
var S1 {i in 1..6} = X[2 - i mod 2, 3 - i mod 3] + X[2 - i mod 2 + 1, 3 - i mod 3];
var S2 {i in 1..6} = X[3 - i mod 3, 2 - i mod 2] + X[3 - i mod 3, 2 - i mod 2 + 1];
var S {i in 1..12} = if i<=6 then S1[i] else S2[i-6];

subject to st: alldiff {i in 1..12} S[i];

option solver jacop;
option jacop_options 'version timing=1 outlev=1 outfreq=10 timelimit=60';

[forest...@gmail.com]

correction model:

param n integer, := 3;

param g integer, := 4+4*n*(n-1);
param K integer, := 2*n*(n-1);
param f integer, := K div 2;

set Z := {3,5,7,11,13,17,19,23};

var X {1..n, 1..n} integer in Z;

var S1 {i in 1..f} = X[2 - i mod 2, 3 - i mod 3] + X[2 - i mod 2 + 1, 3 - i mod 3];
var S2 {i in 1..f} = X[3 - i mod 3, 2 - i mod 2] + X[3 - i mod 3, 2 - i mod 2 + 1];
var S {i in 1..K} = if i<=f then S1[i] else S2[i-f];

subject to c1 : alldiff {i in 1..K} S[i];
subject to c2 {i in 1..K} : S[i] <= g;

#option solver jacop;
#option jacop_options 'version timing=1 outlev=1 outfreq=10 timelimit=60';

#option solver gecode;
#option gecode_options 'outlev=1 outfreq=10 timelimit=60';

#option solver ilogcp;
#option ilogcp_options 'version timing=1 timelimit=30 logperiod=1000000 outlev=verbose';

option solver locsol;
option locsol_options 'version verbosity=normal timing=1 time_between_displays=10 timelimit=60';

solve;
display X;
display S;

Solvers jacop, gecod, ilogcp say "infeasible problem". For solver locsol this model is feasible, but it does not find a solution.

Also not clear - why number of variables is 81?


Feasible solution:

X = [3, 13, 11; 3, 7, 11; 23, 5, 3]

S = [20, 26, 22, 12, 6, 14, 10, 24, 28, 18, 16, 8]

[Victor Zverovich]

The problem was caused by incorrect handling of common expressions (defined variabled) in alldiff. It will be fixed in the next solver update. In the meantime you can move the definition of variable S to a constraint:

  var S {i in 1..K} integer;

  s.t. set_S{i in 1..K}: S[i] = if i<=f then S1[i] else S2[i-f];

HTH,

Victor

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[forest...@gmail.com]

Thanks!

Please tell me, why number of variables (decisions) is 81?

param n integer, := 3;

set N := 1..n;
set N2 := 1..2*(n-1);

param g integer, := 4+4*n*(n-1);

set Z := {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511};

set P := {p in Z : p<=max{i in Z, j in Z : g-i = j}(j)};

var X {N, N} integer in P;
#var X {N, N} integer in 3..23;

var S {i in N2, j in N} = if i<=n-1 then X[i,j] + X[i+1,j] else X[j,i-n+1] + X[j,i-n+2];

subject to c1 : alldiff {i in N2, j in N} S[i,j];

subject to c2 {i in N2, j in N} : S[i,j] <= g;

option solver locsol;
option locsol_options 'version verbosity=normal threads=3 timing=1 time_between_displays=10 timelimit=600000';

solve;

printf "\nX= [";
printf {i in N, j in N} (X[i,j] & (if j < n then "," else (if i<n then ";" else "]\n")));

If in line "var X {N, N} integer in P;" P replace on "3..23", then number of decisions = 9.

[Victor Zverovich]

AMPL adds auxiliary variables for variables taking values from a set. In addition to that, solver interfaces may add variables for common subexpressions and such.

HTH,

Victor

--