Thursday, February 10, 2022

4-color maps: another model

In [1], I discussed coloring all US counties (3,221 of them) such that neighboring counties have a different color. The famous 4-color theorem says we can do this with just 4 colors. After some adventures with the data, I was indeed able to produce maps with 4 colors.


Model 1: US Counties colored with minimum number of colors

An interesting part is the color count table. That table shows the number of counties colored by each color. This is a bit unbalanced. So an obvious question is:

Can we find a 4-coloring that has a more equal use of colors?

To recap, the original graph coloring model looked like:

Model 1: Minimize number of colors model
\[\begin{align} \min & \sum_c \color{darkred}u_c \\ & \sum_c \color{darkred}x_{n,c}=1 &&\forall n \\ & \color{darkred}x_{i,c}+\color{darkred}x_{j,c} \le \color{darkred}u_c && \forall \color{darkblue}{\mathit{arc}}_{i,j}, c \\ & \color{darkred}u_c \le \color{darkred}u_{c-1} && \forall c\gt 1 \\ & \color{darkred}x_{n,\color{darkgreen}{\mathit{color1}}} = 1 && \text{for all isolated counties}\\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & \color{darkred}u_c \in \{0,1\} \end{align} \]

This model delivered 4 as the optimal solution. Now we want to minimize the spread in the color count. We can reuse the original model, and convert the objective into a constraint: \[\sum_c \color{darkred}u_c=4\] but another, probably simpler approach is just to restrict the set \(c\) of colors to just 4 elements.  With this, a model can be:

Model 2: Minimize spread in color count
\[\begin{align} \min\> & \color{darkred}{\mathit{range}} = \color{darkred}{\mathit{maxCount}} -\color{darkred}{\mathit{minCount}}\\ &\color{darkred}{\mathit{maxCount}} \ge \color{darkred}{\mathit{count}}_c && \forall c\\ &\color{darkred}{\mathit{minCount}} \le \color{darkred}{\mathit{count}}_c && \forall c\\ &\color{darkred}{\mathit{count}}_c = \sum_n\color{darkred}x_{n,c} && \forall c\\ & \sum_c \color{darkred}x_{n,c}=1 &&\forall n \\ & \color{darkred}x_{i,c}+\color{darkred}x_{j,c} \le 1 && \forall \color{darkblue}{\mathit{arc}}_{i,j}, c \\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & c = \{\color{darkgreen}{col1},\color{darkgreen}{col2},\color{darkgreen}{col3},\color{darkgreen}{col4}\}  \end{align} \]

Note that:
  • The variable \(\color{darkred}u_c\) is dropped. We know it is 1 if set \(c\) has just 4 colors.
  • Isolated counties now become interesting again: they play a role. We no longer fix them to have color 1.

Symmetry breaking

We can help things a little bit along by fixing one county. I chose the first county, Autauga County, AL (fips code: 01001), and fixed it to have color 1. Now we can look at a neighbor and fix it to color 2.

Alabama counties

I chose Dallas County for that. Then Chilton has to have color 3 or 4. I fixed it to color 3. So altogether, I fixed 3 assignments.

When I run this model, I see:

Model 2: Minimize spread in color count

Obviously, we cannot do better than this.

A variant of this model would be to use the total area occupied by each color, and make those as equal as possible. Data for this is readily available.

Note: I used d3 [2] for visualization here.

The worst spread

One would think that finding the worst spread: one color dominating and another assigned to very few countries, would be just a matter of replacing minimize by maximize. Unfortunately, this is not the case. Finding the max and the min count is now more difficult: we need extra binary variables. The idea is to use the following formulation: \[\color{darkred}y=\max_i \color{darkred}x_i \iff \begin{aligned} & \forall i: \color{darkred}y\ge \color{darkred}x_i\\ & \exists i: \color{darkred}y\le \color{darkred}x_i\end{aligned} \iff \begin{aligned} & \color{darkred}y\ge \color{darkred}x_i &&\forall i \\ & \color{darkred}y\le \color{darkred}x_i - \color{darkblue}M (1-\color{darkred}\delta_i) &&\forall i \\ & \sum_i \color{darkred}\delta_i=1 \\ & \color{darkred}\delta_i \in \{0,1\}\end{aligned} \]

Based on this is my first model:

Model 3a: Maximize spread in color count
\[\begin{align} \max\> & \color{darkred}{\mathit{range}} = \color{darkred}{\mathit{maxCount}} -\color{darkred}{\mathit{minCount}}\\ &\color{darkred}{\mathit{maxCount}} \ge \color{darkred}{\mathit{count}}_c && \forall c \\ &\color{darkred}{\mathit{maxCount}} \le \color{darkred}{\mathit{count}}_c + \color{dakblue}M \color{darkred}\delta^{\mathit{max}}_c&&\forall c \\ & \sum_c \color{darkred}\delta^{\mathit{max}}_c = {\bf{card}}(c)-1 \\ &\color{darkred}{\mathit{minCount}} \le \color{darkred}{\mathit{count}}_c && \forall c \\ &\color{darkred}{\mathit{minCount}} \ge \color{darkred}{\mathit{count}}_c - \color{dakblue}M \color{darkred}\delta^{\mathit{min}}_c&&\forall c \\ & \sum_c \color{darkred}\delta^{\mathit{min}}_c = {\bf{card}}(c)-1 \\ &\color{darkred}{\mathit{count}}_c = \sum_n\color{darkred}x_{n,c} && \forall c\\ & \sum_c \color{darkred}x_{n,c}=1 &&\forall n \\ & \color{darkred}x_{i,c}+\color{darkred}x_{j,c} \le 1 && \forall \color{darkblue}{\mathit{arc}}_{i,j}, c  \\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & \color{darkred}\delta^{\mathit{min}}_c, \color{darkred}\delta^{\mathit{max}}_c \in \{0,1\} \\ & c = \{\color{darkgreen}{col1},\color{darkgreen}{col2},\color{darkgreen}{col3},\color{darkgreen}{col4}\}  \end{align} \]

  • We can set \(\color{darkblue}M := {\bf{card}}(c)\). 
  • We can use the solution of model 1 as incumbent using the mipstart option.
  • This is a very difficult model to solve.

A much better approach is to introduce a symmetry-breaking ordering constraint \[\color{darkred}{\mathit{count}}_c \le \color{darkred}{\mathit{count}}_{c-1}\] and use this to form the objective: \[\max\>\> \color{darkred}{\mathit{range}} = \color{darkred}{\mathit{count}}_{\color{darkgreen}{\mathit{col1}}} - \color{darkred}{\mathit{count}}_{\color{darkgreen}{\mathit{col4}}}\] This leads to the simpler model:

Model 3b: Maximize spread in color count
\[\begin{align} \max\> & \color{darkred}{\mathit{range}} = \color{darkred}{\mathit{count}}_{\color{darkgreen}{\mathit{col1}}} - \color{darkred}{\mathit{count}}_{\color{darkgreen}{\mathit{col4}}}\\  &\color{darkred}{\mathit{count}}_c = \sum_n\color{darkred}x_{n,c} && \forall c\\ & \sum_c \color{darkred}x_{n,c}=1 &&\forall n \\ & \color{darkred}x_{i,c}+\color{darkred}x_{j,c} \le 1 && \forall \color{darkblue}{\mathit{arc}}_{i,j}, c \\ &\color{darkred}{\mathit{count}}_c \le \color{darkred}{\mathit{count}}_{c-1} && \forall c \gt 1 \\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & c = \{\color{darkgreen}{col1},\color{darkgreen}{col2},\color{darkgreen}{col3},\color{darkgreen}{col4}\}  \end{align} \]

Although better than model 3a, this is still a very difficult model to solve. After 2 hours there is still a very large gap, so not even close to proving optimality.

Max spread model (time limit)


A 4-colored map has enough degrees of freedom that we can meaningfully solve for different objectives. Here we minimized and maximized the spread in the number of counties covered by each color. 

The max-spread model is both more challenging to model as well to solve.


  2. Data-Driven Documents,

Appendix: GAMS Model 2


Minimize spread in counties per color

Color map with US counties

ColorCounties.gms (this file)


* data

'nodes: counties (fips code)'
'arcs: adjacency -- upper-triangular part only'
'colors' /
col1  '#96CEB4'
col2  '#FFEEAD'
col3  '#D9534F'
col4  '#FFAD60'
'county names'


* fix data wrt Glades County, FL
* set one of these to "no"
'12043','12085') = no;
*a('12043','12099') = no;

scalar numCounties 'number of counties in map';
numCounties =
display numCounties;


* we have a few isolated counties (Hawaii)
set isolated(n) 'county without neighbors';
isolated(n) =
sum(j$(a(n,j) or a(j,n)),1)=0;
display isolated;

* data checks

abort$(card(map)<>numCounties) "check map";
abort$sum(a(i,j)$(ord(i)>=ord(j)),1) "a(i,j) is not strictly upper-triangular";

* optimization model: minimize number of colors needed

binary variables
'assign color to node'

'number of colors needed'
'number of counties colored with c'

'make number of times each color is used as equal as possible'
'every node should have exactly one color'
'adjacent vertices cannot have the same color'

objective.. range =e= maxCount-minCount;

boundMax(c).. maxCount =g= count(c);
boundMin(c).. minCount =l= count(c);

counting(c).. Count(c) =e=
sum(n, x(n,c));

sum(c, x(n,c)) =e= 1;

notSameColor(a(i,j),c).. x(i,c)+x(j,c) =l= 1;

* fix a few counties by looking at the map
*    01001 . "Autauga County, AL"  -> color 1
* neigbor is: Dallas County:
*    01047 . "Dallas County, AL"   -> color 2
* a neigbor to both is: Chilton
*    01021 . "Chilton County, AL"  -> color 3

'01001','col1') = 1;
'01047','col2') = 1;
'01021','col3') = 1;

model color /all/;
option optcr=0, threads=16;
solve color minimizing range using mip;

display x.l;

parameter colcount(c) 'number of counties with given color';
colcount(c) =
sum(n$(x.l(n,c)>0.5), 1);
display colcount;

No comments:

Post a Comment