[Help-glpk] Why this MIP problem has no feasible solution?
From:
Xie Zhengwei
Subject:
[Help-glpk] Why this MIP problem has no feasible solution?
Date:
Sat, 7 Jun 2008 00:23:04 -0700
Hi, everyone, I have a problem as followed or see attanchment. If I comment hc, vc and objective function line, It works very well. The hc, vc is going to get a = (b & c). b is sum{k in 1..n} node[i,j,k], c is sum{k in 1..n} node[i,j+1,k]. This two sums have been constrained to {0,1}. It is supposed to work here. Thank you in advance.
------------------- param n, integer, >=2;
var node{i in 1..n,j in 1..n,k in 1..n}, binary; var h{i in 1..(n-1),j in 1..(n-1)}, binary; var v{i in 1..(n-1),j in 1..(n-1)}, binary;
s.t. fa{k in 1..n}: sum{i in 1..n,j in 1..n} node[i,j,k] = 1;
/* Node k only occur once and at least once*/
s.t. fb{i in 2..(n-1), j in 2..(n-1), k in 1..n-1}: node[i,j-1,k+1] + node[i,j+1,k+1] + node[i-1,j,k+1] + node[i+1,j,k+1] >= node[i,j,k]; s.t. fb2{j in 2..(n-1), k in 1..n-1}: node[1,j-1,k+1] + node[1,j+1,k+1] + node[2,j,k+1] >= node[1,j,k];
s.t. fb3{j in 2..(n-1), k in 1..n-1}: node[n,j-1,k+1] + node[n,j+1,k+1] + node[n-1,j,k+1] >= node[n,j,k]; s.t. fb4{i in 2..(n-1), k in 1..n-1}: node[i+1,1,k+1] + node[i-1,1,k+1] + node[i,2,k+1] >= node[i,1,k];
s.t. fb5{i in 2..(n-1), k in 1..n-1}: node[i+1,n,k+1] + node[i-1,n,k+1] + node[i,n-1,k+1] >= node[i,n,k]; s.t. fb6{k in 1..n-1}: node[1,2,k+1] + node[2,1,k+1] >= node[1,1,k]; s.t. fb7{k in 1..n-1}: node[1,n-1,k+1] + node[2,n,k+1] >= node[1,n,k];
s.t. fb8{k in 1..n-1}: node[n-1,1,k+1] + node[n,2,k+1] >= node[n,1,k]; s.t. fb9{k in 1..n-1}: node[n-1,n,k+1] + node[n,n-1,k+1] >= node[n,n,k];
s.t. fc{i in 1..n,j in 1..n}: sum{k in 1..n} node[i,j,k] <= 1;
/* Every site only have one node on it*/ s.t. hc{i in 1..(n-1), j in 1..(n-1)}: -1 <= 2*(sum{k in 1..n} node[i,j,k]) + 2*(sum{k in 1..n} node[i,j+1,k])-4*h[i,j] <=3; s.t. vc{i in 1..(n-1), j in 1..(n-1)}: -1 <= 2*(sum{k in 1..n} node[i,j,k]) + 2*(sum{k in 1..n} node[i+1,j,k])-4*h[i,j] <=3;
s.t. start: node[1,1,1] = 1;
maximize Z: sum{i in 1..(n-1),j in 1..(n-1)} h[i,j] + sum{i in 1..(n-1),j in 1..(n-1)} v[i,j]; solve;
for {i in 1..n} { for {j in 1..n} { printf " %d", sum{k in 1..n} node[i,j,k] * k;
} printf "\n"; } printf "Edges\n"; for {i in 1..(n-1)} { for {j in 1..(n-1)} { printf " %d", sum{k in 1..n} node[i,j,k]+sum{k in 1..n} node[i,j+1,k];
} printf "\n"; }