The Fermat-Torricelli problem is one of the most interesting in optimization theory. The classical version of this problem is about finding the point inside a triangle that is the minimum distance to its three vertices. The problem was proposed by Pierre de Fermat and solved by Evangelista Torricelli, who provided actually several solutions to the problem. A more generalized version of the problem tries to find the point \((x^\ast,y^\ast)\) in a triangle with vertices \((x_1,y_1)\), \((x_2,y_2)\), and \((x_3,y_3)\) that minimizes the function \[ F(x,y)=\sum_{i=1}^3 w_i \sqrt{(x_i-x)^2+(y_i-y)^2} \] where \(w_i\) are weights. When these weights are all equal to one, minimizing function \(F(x,y)\) solves the classic Fermat-Torricelli problem. When the weights are different, minimizing \(F(x,y)\) solves a transportation problem that is also known as the Steiner problem, or the railway junction problem. In this case, point \((x^\ast,y^\ast)\) minimizes transportation costs when \(w_i\) are the volume of traffic originating from vertex \(i\).

Several approaches are known that find \((x^\ast,y^\ast)\) numerically and iteratively. But recently a Russian mathematician, Alexei Yur'evich Uteshev from Saint-Petersburg State University, published a paper Analytical Solution to the Generalized Fermat-Torricelli Problem in The American Mathematical Monthly 121(4) April 2014 that provides a nifty analytical solution to the problem. An earlier version of his paper is also available on arXiv.

The illustration on the right shows an example. A triangle with three vertices (P1, P2, P3) can be thought of as three cities. We now want to build three highways originating in each city and meet in P*. The thickness of the green lines reflects the capacity each highway segement is expected to handle. As is visible in the illustration, the larger traffic volume originating in P3 "pulls" the point P* where the highways meet closer to P3. Because there is also more traffic originating from P2 than P1, the junction P* is closer to the line segement P2–P3 than to P1–P3.

I got interested in the Fermat-Torricelli problem because it is solves a class of transport optimization problems, also in electric grid design. If the weights in the above problem reflect traffic volume (or electric loads), then \(w_1= v_{12}+v_{13}\), \(w_2= v_{12}+v_{23}\), and \(w_3= v_{13}+v_{23}\). In simple terms, each of the three segments that connect to point P* must handle the sum of the traffic that forks off to the other two points. It is interesting to note that this variation of the problem can have solutions where P* is almost (but not exactly) on one of the line segments that connects the triangle vertices, with the "spur line" branching off perpendicularly. For example, if \(v_{23}\) is very large compared to \(v_{12}+v_{13}\), then \(w_1\) is small and both \(w_2\) and \(w_3\) are relatively large.

Another interesting variation of the Fermat-Torricelli problem is to think about the redundancy that is built into a network that connected all three vertices (the blue lines in the diagram above). If a network is connecting through a central hub, failure of any of the hub connectors (the green lines in the diagram) stops all traffic. While a network consisting of only blues lines is more expensive, it tends to be more robust. For example, if P2–P3 fails, traffic from P2 to P3 can be rerouted through P1. A network that is prone to disruptions would probably favour this then a less costly but "buggy" network. The cost of outage would have to be added to the optimization problem to get the "right" answer. In other words, uncertainty matters when it comes to economical solutions.

Below is a code fragment in the SAS matrix language that reads in a database of triangle coordinates and weights and writes out a database with the Fermat-Torricelli points. The code also handles the cases where an interior solution does not exist. When the weights for one vertex are too large, that vertex may become the optimal point. Intuitively, if most traffic is to and from point P3, it is not necessary to build a highway between P1 and P2.

The code below tries to be efficient about some of the calculations. The distances between points appear as their squares (e.g., r12s) rather than as actual distances. This speeds up computation. The output from the IML code provides the coordinates of the optimal Fermat-Torricelli point \((x^\ast,y^\ast)\) as well as the value of \(F(x^\ast,y^\ast)\). Below the SAS macro are a few sample calculations for testing. Example9 corresponds to the points in the SVG diagram above.

With this somewhat esoteric blog written on Christmas eve, I wish everyone a Merry Christmas 2014. May the world find peace and love.