Multiple Solutions in Minimum Spanning Tree example

In [1], I discussed some LP and MIP formulations for the Minimum Spanning Tree (MST) problem. 

Minimum Spanning Tree visualized through Google Maps

Here, I focus on two formulations: a multicommodity network approach (this can be solved as a large LP) and a MIP formulation based on techniques we know from the Traveling Salesman Problem (TSP). The main issue I want to discuss is the presence of multiple optimal solutions.

Circle Packing and HTML reporting

Little example. Here, we try to pack \(n\) circles with a given radius \(r_i\) into a larger disc with an unknown radius \(R\). The goal is to minimize \(R\). The underlying model is simple: 

Packing of Circles
\[\begin{align} \min\> & \color{darkred}R \\ & \sum_c \left(\color{darkred}p_{i,c}-\color{darkred}p_{j,c}\right)^2 \ge \left(\color{darkblue}r_i+\color{darkblue}r_j\right)^2 & \forall i\lt j \\ & \sum_c \color{darkred}p_{i,c}^2 \le \left(\color{darkred}R-\color{darkblue}r_i\right)^2 & \forall i \\ & \color{darkred}R \ge 0\\ & c \in \{x,y\} \\ \end{align}\]

Water

• Fascinating map with annual water throughput. 
• This is related to water availability for irrigation. An important topic.
• The Rio Grande is not so grand here.
• It must not be completely trivial to produce this map.
• See: 
  Peter Gleick and Matthew Heberger, American Rivers: A Graphic, https://pacinst.org/american-rivers-a-graphic/

MAX-CUT

The MAX-CUT problem is quite famous [1]. It can be stated as follows:

Given an undirected graph \(G=(V,E)\), split the nodes into two sets. Maximize the number of edges that have one node in each set.

Here is an example using a random sparse graph:

Pictures don't match

The Financial Times had an interesting picture of per capita excess deaths. In many respects, this is the best measure to compare how severe different countries are hit by the Coronavirus.

Here is the post [1]:

However, when we go to the corresponding FT page [2], we actually see a different graph:

I suspect the first picture is wrong w.r.t. Spain.

Indeed in a PS of the FT page [2] we see:

This article has been amended to take into account a one-off revision to Spanish data on Thursday. This meant the UK now has the second-highest death rate from coronavirus after Spain rather than the highest rate as originally reported. This article has been modified to replace a chart linking excess deaths to lockdown dates with one linking excess deaths per million.

Looking at the complete picture: 

I am wondering about the difference between the first (total excess deaths per capita) with the last (percentage difference with average). I expected these to be more similar. Could it be that Peru has a low death rate (younger population)?  Again the text has a note on this:

Peru has seen a large rise in deaths this year partly because it has had to battle other diseases, in addition to coronavirus, with its overstretched health system. 

References

1. UK has Europe's highest excess death toll and second highest in the world, https://www.youtube.com/post/UgxDGaBKDom1wrc91fp4AaABCQ
2. UK suffers second-highest death rate from coronavirus, https://www.ft.com/content/6b4c784e-c259-4ca4-9a82-648ffde71bf0