I've learned this game few time ago, but using the capacity of residents
in each building as coefficient values in the objective...
Just for fun, i've adapted the Xypron model to be more short and
flexible.
Now its possible to set the quantity of building colours (showed as
numbers).
See buildings2.mod and buildings3.mod attached.
I've made the buildings3.mod to demonstrate GMPL tips, removing
the unused vars. This is the same that is done (fast) by glpk
presolver,
but in bigger models (with large amount f data) this modeling practice
can save a lot of memory consumption. But, in other hand, the model
can be less "human readable".
Hugs,
Luiz Bettoni
Em 23-12--28158 16:59, nicolas66 escreveu:
Oh I just wanted to know the little trick to express the constraint on red
buildings :/. I have another deeper question: is it a known problem ? If so,
I would be very curious to know the complexities of this problem when the
number of colors (k) is fixed (in particular when k=2, k=3 and beyond).
Thanks a lot for your quick help.
xypron wrote:
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;
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
|
buildings2.mod