© Frauke Jansen, MATH+
Author: Fabian Altekrüger (HU Berlin)
Project: Convolutional Proximal Neural Networks for Solving Inverse Problems (EF 3-7)
Challenge
Every year, Santa encounters the same kind of problem, when he and his helpers organize the transport of the presents to all the children of the world… The elves are supposed to bring the presents from the Christmas factories (F) to secret warehouses (W) on every continent.
F1: This year a secret outpost (F1) in the north of Canada was used to produce 500 loads of presents,
F2: since the main factory (F2) at the north pole has had production problems such that only 400 loads of presents were produced there.
F3: A third factory (F3) at the south pole produced 900 loads of presents.
Although the secret warehouses are already quite well-stocked, some presents are still missing:
W1: in the warehouse in North America (W1) 100 loads are missing;
W2: in South America (W2) 450 loads are missing;
W3: in Africa (W3) 300 loads are missing;
W4: in Australia (W4) 400 loads are missing;
W5: in Europe (W5) 200 loads are missing, and
W6: in Asia (W6) 350 loads are missing.
Since the year was already exhausting enough, and Santa does not want his elves to work overtime, they are searching for an optimal present transport plan from the factories to the secret warehouses minimizing the flight hours. For this purpose, Santa prepares a table containing the travel times (in hours) from each factory to each of the warehouses (see Table 1), taking into account that the factory in Canada (F1) does not produce the correct presents for the warehouses in Africa (W3) and Australia (W4):
| W1 | W2 | W3 | W4 | W5 | W6 | |
|---|---|---|---|---|---|---|
| F1 | 2 | 4 | – | – | 5 | 8 |
| F2 | 7 | 8 | 8 | 11 | 3 | 5 |
| F3 | 8 | 6 | 5 | 4 | 9 | 9 |
Table 1: The flight durations from each factory (F) to each warehouse (W). No flights are operating from (F1) to (W3) and (W4).
Only 1 load per flight can be transported from one factory to one warehouse. The empty planes are flown back to the factories by a subcontractor called MIRACLE TRANSPORT at a fixed rate, such that there are always enough planes at each factory and the duration of these return trips is not considered in the flight duration Santa wants to minimize.
Still, this task seems a bit to complicated for poor old Santa… Can you help him? What is the minimal total flight duration needed to transport all presents from the factories to the secret warehouses?
Possible answers:
- 8080 h
- 8090 h
- 8100 h
- 8110 h
- 8120 h
- 8130 h
- 8140 h
- 8150 h
- 8160 h
- 8170 h
Project reference:
Optimal Transport (OT) is a theory that emerged from the analytical description of the classical transportation problem, in which objects (here presents) are to be distributed optimally (i. e., cost minimizing) from different supply points (here the factories) to different demand points (here warehouses). In our example, the costs are given by the flight duration.
As part of project EF 3-7 Convolutional Proximal Neural Networks for Solving Inverse Problems, I have been working on the 2-Wasserstein distance, which is a special case of the OT problem. We use the 2-Wasserstein distance as a regularizer in inverse problems to compare empirical image distributions.