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.

A multi-objective nonlinear integer programming problem

Picture of the efficient points

In [1], a small multi-objective non-convex MINLP problem is stated:

Let's see how one could approach a problem like this.

Stacking 3d boxes under rotation

Boston custom house tower

Assume we have an infinite collection of 3d boxes of different sizes. As an example let's use [1]:

----     30 PARAMETER boxes  available box sizes

          size-x      size-y      size-z

box1           4           6           7
box2           1           2           3
box3           4           5           6
box4          10          12          32

We want to build a tower of boxes such that the base of the box on top is strictly smaller than the underlying box. The "strictly" part is essential. Otherwise, we can just repeat the same type of box ad infinitum. The interesting angle is: we can rotate the boxes. Without loss of generality, we can assume that for all boxes, after rotation, we have: the width (\(x\)) is less than the depth \((y\)). (This may require a bit of thinking). With this, any box can be placed in just three different ways. 

3d rotations

The objective is to build a tower that is as tall as possible. In [1], this problem is solved using a Dynamic Programming algorithm. Here I want to see how this looks using a MIP model.

2d knapsack problem

This post is about what sometimes is called a 2d knapsack problem. It can also be considered as a bin-packing problem. These are famously difficult problems, so let's have a look at a relatively small instance. 

So, we have one 2d container of a given size. Furthermore, we have a collection of items: rectangles of a given size, with a value. The goal is to pack items in our container without overlapping each other such that the total value is maximized.

To make things concrete, let's have a look at a small data set (randomly generated):

----     18 PARAMETER data  problem data

                width      height   available       value  value/size

k1             20.000       4.000       2.000     338.984       4.237
k2             12.000      17.000       6.000     849.246       4.163
k3             20.000      12.000       2.000     524.022       2.183
k4             16.000       7.000       9.000     263.303       2.351
k5              3.000       6.000       3.000     113.436       6.302
k6             13.000       5.000       3.000     551.072       8.478
k7              4.000       7.000       6.000      86.166       3.077
k8              6.000      18.000       8.000     755.094       6.992
k9             14.000       2.000       7.000     223.516       7.983
k10             9.000      11.000       5.000     369.560       3.733
container      30.000      20.000