Re: [Help-glpk] Constraints and conditions

[nicolas66]

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
> 
> 

-- 
View this message in context: 
http://www.nabble.com/Constraints-and-conditions-tp23449934p23452016.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.