## Wednesday, July 12, 2023

### Coloring edges of a grid

This is a little coloring problem from [1]:

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)

Let's try to build a GAMS model for this. The question itself is not so interesting, but the modeling for setting up these grids is.

### Data structures

First, we need to represent the grid.

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

There are many ways to do this. Here is one. Each grid point is resented by its $$x$$ and $$y$$ coordinate, here denoted by $$(i,j)$$. Edges connect two points, so we get $$(i,j,i',j')$$ to represent $$(i,j) \rightarrow (i',j')$$. We only need two edges leaving for each point: one to the right and one to above. This is done by:

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

The model itself is not super complicated.