Given an m * n grid, each edge must be colored. However, there are 2 constraints:
- Entire grid must use only 3 unique colors
- Each square in the grid must be colored using exactly 2 colors (2 edges per color)
Data structures
*------------------------------------------------- set |
edges(i,j,i+1,j) = yes;edges(i,j,i,j+1) = yes;
When we display this (for a smaller example) we see:
---- 31 SET i grid x-coordinate i1, i2, i3 ---- 31 SET j grid y-coordinate j1, j2, j3 ---- 31 SET edges connects two points i1.j1.i1.j2, i1.j1.i2.j1, i1.j2.i1.j3, i1.j2.i2.j2, i1.j3.i2.j3, i2.j1.i2.j2, i2.j1.i3.j1, i2.j2.i2.j3 i2.j2.i3.j2, i2.j3.i3.j3, i3.j1.i3.j2, i3.j2.i3.j3
I don't use a different numbering scheme for the squares but instead use the coordinates of the left-lower point. We drop the points on the right and upper edge of the grid. This is done by:
squares(i-1,j-1) = yes;
The tricky indexing removes the last row and column. The display confirms this:
---- 31 SET squares numbering of squares j1 j2 i1 YES YES i2 YES YES
I also want to map between squares \((i,j)\) and the corresponding four edges \((i',j')\rightarrow (i'',j'')\). So I generate this crazy 6-dimensional structure semap (for squares-edge map). A square \((i,j)\) has two edges leaving from \((i,j\)) and two edges arriving at \((i+1,j+1)\). That is what I use here:
semap(squares(i,j),edges(i,j,ii,jj)) = yes;
semap(squares(i,j),edges(ii,jj,i+1,j+1)) = yes;
I could have dropped the word edges here, as they don't filter anything out. I left it for clarity.
---- 31 SET semap map between squares and edges i1.j1.i1.j1.i1.j2, i1.j1.i1.j1.i2.j1, i1.j1.i1.j2.i2.j2, i1.j1.i2.j1.i2.j2, i1.j2.i1.j2.i1.j3, i1.j2.i1.j2.i2.j2 i1.j2.i1.j3.i2.j3, i1.j2.i2.j2.i2.j3, i2.j1.i2.j1.i2.j2, i2.j1.i2.j1.i3.j1, i2.j1.i2.j2.i3.j2, i2.j1.i3.j1.i3.j2 i2.j2.i2.j2.i2.j3, i2.j2.i2.j2.i3.j2, i2.j2.i2.j3.i3.j3, i2.j2.i3.j2.i3.j3
Of course, this is just one possible approach. Another would be to use a one-dimensional numbering scheme for edges and squares. You still need to specify which edges are used by a square.
Model
*------------------------------------------------- |
We don't have an objective: we only need to find a feasible solution. In GAMS that means that we use a dummy objective.
- If any of the edges has color \(c\), then the square includes color \(c\)
- If all of the edges don't have color \(c\), then the square does not include color \(c\)
Solution printing
---- 77 PARAMETER solution i1.j1.i1.j2 GREEN, i1.j1.i2.j1 GREEN, i1.j2.i1.j3 RED, i1.j2.i2.j2 RED, i1.j3.i2.j3 BLUE, i2.j1.i2.j2 RED i2.j1.i3.j1 BLUE, i2.j2.i2.j3 BLUE, i2.j2.i3.j2 RED, i2.j3.i3.j3 RED, i3.j1.i3.j2 RED, i3.j2.i3.j3 RED
A little bit of a low-tech solution: just write out the HTML using the PUT statement. However, it is difficult to beat the simplicity of this approach.
A faster 100x100 model
It is interesting that combining models 1 and 2 produces faster results than just model 2.
Counting solutions
--- Cplex Time: 5.94sec (det. 4774.48 ticks)--- Dumping 373248 solutions from the solution pool...
For a 4x5 grid this becomes:
--- Cplex Time: 440.67sec (det. 167328.64 ticks)
--- Dumping 8957952 solutions from the solution pool...
Conclusion
References
- Given an m * n grid, each edge must be colored. However, there are constraints, https://stackoverflow.com/questions/76645751/given-an-m-n-grid-each-edge-must-be-colored-however-there-are-constraints
Appendix: complete GAMS model
$ontext
Color edges of a grid. From https://stackoverflow.com/questions/76645751/given-an-m-n-grid-each-edge-must-be-colored-however-there-are-constraints
Given an m * n grid, each edge must be colored. However, there are 2 constraints:
1. Entire grid must use only 3 unique colors 2. Each square in the grid must be colored using exactly 2 colors (2 edges per color) Model 1: forget 2 edges per color Model 2: add 2 edges per color Model 3: combine models 1 and 2
$offText
*------------------------------------------------- * sets to represent grid and edges. * representation of squares is by left-lower point *-------------------------------------------------
set i 'grid x-coordinate' /i1*i10/ j 'grid y-coordinate' /j1*j10/ edges(i,j,i,j) 'connects two points' squares(i,j) 'numbering of squares' semap(i,j,i,j,i,j) 'map between squares and edges' c 'colors' /red,green,blue/ ;
alias (i,ii),(j,jj);
edges(i,j,i+1,j) = yes; edges(i,j,i,j+1) = yes;
squares(i-1,j-1) = yes;
semap(squares(i,j),edges(i,j,ii,jj)) = yes; semap(squares(i,j),edges(ii,jj,i+1,j+1)) = yes;
option edges:0:0:8,semap:0:0:6; display i,j,edges,squares,semap;
*------------------------------------------------- * MIP model 1 * ignore two edges per color in a square *-------------------------------------------------
variables z 'dummy objective' x(i,j,i,j,c) 'edge colors' sqCol(i,j,c) 'square colors' ; binary variable x,sqCol;
Equations dummyObj oneColor(i,j,i,j) 'an edge has exactly one color' implication1(i,j,i,j,i,j,c) 'ecol(edge,c)=1 for any edge => sqcol(square,c)=1' implication2(i,j,c) 'ecol(edge,c)=0 for all edges => sqcol(square,c)=0' squareColors(i,j) 'exactly 2 colors per square' ;
dummyobj.. z =e= 0;
onecolor(edges).. sum(c, x(edges,c)) =e= 1; implication1(squares,edges,c)$semap(squares,edges).. sqcol(squares,c) =g= x(edges,c); implication2(squares,c).. sqcol(squares,c) =l= sum(semap(squares,edges), x(edges,c)); squarecolors(squares).. sum(c, sqcol(squares,c)) =e= 2;
model coloring1 /all/; solve coloring1 using mip minimizing z; *------------------------------------------------- * MIP model 2 * add two edges per color in a square *-------------------------------------------------
binary variables ZeroOrTwo(i,j,c) 'zero or two edges per color';
equation squareColors2(i,j,c) 'exactly 2 colors per square, and two edges per color';
squareColors2(squares,c).. sum(semap(squares,edges),x(edges,c)) =e= 2*ZeroOrTwo(squares,c);
model coloring2 /dummyObj,oneColor,squareColors2/; option threads=0; *solve coloring2 using mip minimizing z;
*------------------------------------------------- * MIP model 3 * add two edges per color in a square *-------------------------------------------------
model coloring3 /all/; *solve coloring3 using mip minimizing z;
*------------------------------------------------- * print solution *-------------------------------------------------
acronym RED,GREEN,BLUE; parameter col(c) / red RED, green GREEN, blue BLUE/ solution(i,j,i,j) ;
loop(c, solution(edges)$(x.l(edges,c)>0.5) = col(c); );
option solution:0:0:8; display solution;
*------------------------------------------------- * draw solution *-------------------------------------------------
file f /solution.html/; put f;
put '<svg width=800 height=800 viewbox = "0 0 ',(card(i)+1):0:0,' ',(card(j)+1):0:0,'">'/; loop(edges(i,j,ii,jj), loop(c$(x.l(edges,c)>0.5), put '<line x1=',ord(i):0:0,' x2=',ord(ii):0:0,' y1=',ord(j):0:0,' y2=',ord(jj):0:0,' stroke="',c.tl:0,'" stroke-width="0.07"/>'/; ) ) put '</svg>'/;
execute "shellexecute solution.html"; |
The source question asks for the number of possible solutions instead of a feasible one. I think it is not hard to construct a feasible solution: like all vertical edges in color 1, left half of horizontal edges in color 2, and right half of horiziontal edges in color 3. I don't know if it is possible to count the solutions by excluding the solutions one-by-one and re-solve the problem, since the number seems to be quite large.
ReplyDeleteJust use the solution pool, using exactly the same models. This number will explode quickly.
DeleteThis comment has been removed by the author.
ReplyDelete