Alexander Schrijver and the history of the transportation and maximum flow problems

3484
Alexander Schrijver @EURO2015 - Image by Guy Hinks. (EURO2015)

Alexander Schrijver @EURO2015 – Image by Guy Hinks. (EURO2015)

Last month, Alexander Schrijver was awarded the EURO Gold Medal 2015. The award is considered the highest European distinction in Operations Research (OR). The presentation of the award at the EURO 2015 Conference in Glasgow was followed by an inspiring speech from the laureate himself. He spoke about the history of transportation and maximum flow problems and his research on these topics, both of which are central to the OR field.

While most sources state that operations research emerged around 1940 – not coincidentally around the time of World War II – Schrijver has found a significantly older paper that points towards an earlier origin. He showed that in 1930, the Russian A.N. Tolstoı had already published an article on the transportation problem. Tolstoı’s article describes several solution approaches, and recognizes that an optimal solution can not contain negative-cost cycles in its residual graph. Thereby, it lays the foundation for negative-cycle cancelling algorithms that are still in use today. All in perfectly good Russian, of course.

Schrijver also talked about a solution which addressed cargo transportation along the Soviet Union railway network using an approach detailed in Tolstoi’s paper. At the time, this was considered a large-scale transportation problem (10 sources and 68 destinations). Tolstoı claimed to have solved the problem to optimality, a solution we can now verify with modern linear programming tools.

As Schrijver continued, he drew our attention to another interesting paper. This paper, referenced by the famous Ford and Fulkerson as ‘secret’, raised some fascinating questions. The paper turned out to be a report from 1955, written for the US Air Force. The report remained classified for decades – up until the late nineties. It was eventually declassified following Schrijver’s request to the Pentagon. Schrijver shared the content of the paper with an enthralled audience, spicing up the story even further by revealing the names of former American spies in the process.

The paper studied the exact same Russian railway system that Tolstoı wrote about in his study. However, coming from an American point of view, the problem was formulated somewhat differently. In fact, their objective was to find a minimum cut in the network, which they described as ‘the bottleneck’. They proved optimality by showing the existence of a flow with the same value as their obtained cut.

This story highlights once again that the origin of operations research is highly intertwined with military operations. Moreover, it shows that the concept of duality – in this case leading to Ford Fulkerson’s ‘max-flow min-cut theorem’ – has been around since the early days of optimization.

Schrijver’s presentation slides can be found on the website of the Association of European Operational Research Societies.

For Schrijver’s paper on the history of the transportation and maximum flow problems, see http://homepages.cwi.nl/~lex/files/histtrpclean.pdf

Alexander Schrijver is known by the general public for his work on scheduling the Dutch railway system. Schrijver has received many awards for his work and he is a Knight in the Order of the Netherlands Lion.

· · · ·
http://www.ortec.com

Caroline Jagtenberg

Caroline Jagtenberg has a background in Physics and Mathematics, both of which she studied at the University of Utrecht. She has also spent periods at Lund University in Sweden and Monash University in Australia. She currently works three days a week as a PhD student at CWI (The Centre for Mathematics & IT) in Amsterdam, where as part of the REPRO project she’s undertaking research into operational ambulance planning: investigating on the one hand the proactive repositioning of unoccupied ambulances and on the other whether sending the nearest ambulance is always the best option.

Besides her work at CWI, Caroline is a part-time software engineer at ORTEC, where she develops methods for efficient personnel planning. For this she uses forecasting methods she developed herself that, on the basis of historical volumes, determine how many staff will be needed in the future.

Leave a Comment

Your email address will not be published. Required fields are marked *