Re: [Help-glpk] Constraints and conditions

[Xypron]

nicolas66 wrote:
> For a project I'm working on, I need to solve the following problem. ...
>   
Hello Nicolas,

see my model below.

Best regards

Xypron

# Problem posed by Nicolas
#
# Suppose we have a squared-grid (size=n) with n2 cells with a 4-connexity
# neighborhood. Each cell must contains exactly one building. We have 
several
# building colors (blue, red and green) with an increasing amount of points.
# The game rules are the following:
#
# * No constraints on blue buildings.
# * Red buildings must have at least one blue building in its neighborhood.
# * Green buildings must have at least one red building and at least one 
blue
# building in its neighborhood.
#
# The goal is to maximize the number of points by having the biggest 
buildings
# (green > red > blue).

# size of problem
param n := 5;
# set of positions including edges
set N := 0 .. n+1;
# set of positions without edges
set N0 := 1 .. n;

# binaries indicating color;
var is_blue{i in N, j in N}, binary;
var is_green{i in N, j in N}, binary;
var is_red{i in N, j in N}, binary;

# color counts
var blues;
var greens;
var reds;

# Objective
maximize obj :
(n+1)**4 * greens + (n+1)**2 * reds + blues;

# set boundaries to 0
s.t. blueN{i in N} :
is_blue[i,0] = 0;
s.t. blueW{i in N} :
is_blue[0,i] = 0;
s.t. blueE{i in N} :
is_blue[n+1,i] = 0;
s.t. blueS{i in N} :
is_blue[i,n+1] = 0;

s.t. redN{i in N} :
is_red[i,0] = 0;
s.t. redW{i in N} :
is_red[0,i] = 0;
s.t. redE{i in N} :
is_red[n+1,i] = 0;
s.t. redS{i in N} :
is_red[i,n+1] = 0;

s.t. greenN{i in N} :
is_green[i,0] = 0;
s.t. greenW{i in N} :
is_green[0,i] = 0;
s.t. greenE{i in N} :
is_green[n+1,i] = 0;
s.t. greenS{i in N} :
is_green[i,n+1] = 0;

# max one color per cell
s.t. sumCell{i in N, j in N} :
is_blue[i,j] + is_green[i,j] + is_red[i,j] <= 1;

# Red buildings must have at least one blue building in its neighborhood.
s.t. redNH{i in N0, j in N0} :
is_red[i,j] <= is_blue[i-1,j] + is_blue[i+1,j] + is_blue[i,j-1] + 
is_blue[i,j+1];

# Green buildings must have at least one red building
# and at least one blue building in its neighborhood.
s.t. greenNH1{i in N0, j in N0} :
is_green[i,j] <= is_red[i-1,j] + is_red[i+1,j] + is_red[i,j-1] + 
is_red[i,j+1];
s.t. greenNH2{i in N0, j in N0} :
is_green[i,j] <= is_blue[i-1,j] + is_blue[i+1,j] + is_blue[i,j-1] + 
is_blue[i,j+1];

# Color count
s.t. sumBlue :
blues = sum{i in N0, j in N0} is_blue[i,j];
s.t. sumGreen :
greens = sum{i in N0, j in N0} is_green[i,j];
s.t. sumRed :
reds = sum{i in N0, j in N0} is_red[i,j];

solve;

# output
for{i in N0}
{
for{j in N0}
{
printf if is_green[i,j] then 'G'
else if is_blue[i,j] then 'B'
else if is_red[i,j] then 'R'
else ' ';
}
printf "\n";
}
end;