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?

Is a heuristic a solver?

Can we call a heuristic (especially a meta-heuristic) a solver? I am not so sure.

Warning: this is somewhat of an opinionated rant. Many of you may not agree.

The name "solver" seems to imply that the underlying algorithm knows when an optimization problem is solved. By that I mean: it can stop at some stage and report "solved". Meta-heuristics typically don't have a clue about optimality, and just keep on churning until hitting some form of time or iteration limit. (One could devise some stopping criteria basic on stochastic reasoning, but that is not often used in meta-heuristics).

So my proposal is:

Heuristics (including meta-heuristics) should not be called solvers. They don't know when a problem is solved.

A different coloring problem

In [1] the following problem is proposed:

• Consider a complete (undirected) graph,
• where each arc has a weight.
• Given a collection of colors, color each node,
• such that the sum of the weights of arcs with same-colored nodes is minimized.
• We can assume some sparsity in the weights. 

The user expects the number of nodes to be between 20 and 50, and there are just a small number of colors.

Minimize weights for the colored arcs

The picture shows a complete graph (all nodes have a direct arc to each other) with 10 nodes. The optimal coloring of nodes minimizes the sum of weights along the colored edges. An edge is colored if the two incident nodes have the same color. 

Coloring the US county map

A famous result in graph theory is that we can color a planar graph with just four colors [1]. The MIP model for coloring a graph is really simple. Let's try this with a relatively large data set: the map of US counties. We'll see that there are some hurdles on the way.

Building block: MIP model for coloring a graph

The problem is as follows: we want to assign a color to each node such that nodes connected by an arc don't have the same color. The objective is to minimize the number of different colors. For the MIP model we use an assignment variable:  \[\color{darkred}x_{n,c} = \begin{cases}1 & \text{if node $n$ gets color $c$} \\  0 & \text{otherwise}\end{cases}\] To keep track of the colors we have: \[\color{darkred}u_c = \begin{cases}1 & \text{color $c$ is used for some nodes} \\ 0 & \text{otherwise}\end{cases}\]

The MIP model can look like:

MIP 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,c} \in \{0,1\} \\ & \color{darkred}u_c \in \{0,1\} \end{align} \]

An All-Paths Network Problem

In [1] a graph problem is proposed:

• Given an undirected network,
• Find all paths between two nodes,
• Such that no arc is used more than once,
• And the path does not contain more than \(M\) arcs

Notice that nodes can be visited several times. I thought this could be a good job for a solution pool approach. 

Preliminaries

As I am more familiar with directed graphs, let's start with setting up a small random, sparse, directed graph. 

I start with 10 nodes and say there is a 20% probability that a link exists between two nodes, \(i \rightarrow j\). So the data set looks like:

----     30 SET n  nodes  n1 ,    n2 ,    n3 ,    n4 ,    n5 ,    n6 ,    n7 ,    n8 ,    n9 ,    n10  ----     30 SET a  directed arcs             n1          n2          n3          n4          n5          n6 n1                     YES                     YES n2                                                                     YES n3                                 YES n4                                 YES         YES                     YES n6                                                         YES n7         YES                                             YES n8                                 YES n9         YES  +          n7          n8          n9         n10 n1                     YES n2                     YES n3                     YES         YES n4         YES n5                                 YES n6                                             YES n8                                             YES n9         YES                                 YES

Using \(n_1\) as the start node and \(n_{10}\) as the end node, we can visualize this as:

Importing JSON files into GAMS

JSON (JavaScript Object Notation) files [1] provide a flexible and simple way to store and exchange data. It is text, so we can easily look at it. JSON files typically have the extension .json. (using it may help syntax coloring in editors). JSON can represent rather complex tree-like data structures that may require some work to convert into simpler formats such as tabular data. 

EIA (U.S. Energy Information Administration) provides bulk data in JSON format [2]. These files are not strictly JSON. They have a .txt extension. Basically, each line is a JSON object. 

To make it a proper JSON file one would have to wrap this into an array.

MacMahon Squares

Percy Alexander MacMahon [1]

This post is about a puzzle designed by Percy Alexander MacMahon [1] and described in a book published in 1921 [2].

Solve status: not as easy as it looks

In [1] a question was asked about a solve status in CVXR when we hit a time limit. Hopefully, we obtain the best solution found so far. But do we also get some indication about the status of this solution? CVXR only has the following status codes [2]:

status The status of the solution. Can be "optimal", "optimal_inaccurate", "infeasible", "infeasible_inaccurate", "unbounded", "unbounded_inaccurate", or "solver_error".

That looks wholly inadequate to properly describe this situation.

Shortest path in GAMS

Here is a presentation for a GAMS workshop. We focus on the Shortest Path LP problem. I use this model to discuss a lot of different things:

• Modeling networks in GAMS
• Sparse data structures in GAMS
• Random number generation
• Python and GAMS
• Put facility
• Visualization (Python and HTML/Javascript based) 

Example Visualization of a Shortest Path in a Network

Transportation Model (sharing a PowerPoint presentation)

trnsport.gms is the first model in the GAMS model library. Here I am using it to give an introduction in GAMS. The PowerPoint presentation has three major sections:

• the historical importance of the transportation model in economics (Nobel prizes have been earned),
• a quick introduction to the GAMS language and the GAMS listing file,
• a nerdy section (optional) about recognizing a basis and an optimal solution in the listing file.