Tropical Algebra and Railway Optimization
Posted by John Baez
Simon Willerton pointed out a wonderful workshop, which unfortunately neither he nor I can attend… nor Jamie Vicary, who is usually at Birmingham these days:
- Tropical Mathematics & Optimisation for Railways, University of Birmingham, School of Engineering, Monday 18 June 2018.
If you can go, please do — and report back!
Let me explain why it’s so cool…
Tropical algebra involves the numbers made into a rig with minimization as the addition and addition as the multiplication.
Tropical algebra is important in algebraic geometry, because if you take some polynomial equations and rewrite them replacing + with min and × with +, you get equations that describe shapes with flat pieces replacing curved surfaces, like this:
These simplified shapes are easier to deal with, but they shed light on the original curved ones! Click the picture for more on the subject from Johannes Rau.
Tropical algebra is also important for quantization, since classical mechanics chooses the path with minimum action while quantum mechanics sums over paths. But it’s also important for creating efficient railway time-tables, where you’re trying to minimize the total time it takes to get from one place to another. Finally these worlds are meeting!
Here’s the abstract, which shows that the reference to railway optimization is not just a joke:
Abstract. The main purpose of this workshop is to bring together specialists in tropical mathematics and mathematical optimisation applied in railway engineering and to foster further collaboration between them. It is inspired by some applications of tropical mathematics to the analysis of railway timetables. The most elementary of them is based on a controlled tropically linear dynamic system, which allows for a stability analysis of a regular timetable and can model the delay propagation. Tropical (max-plus) switching systems are one of the extensions of this elementary model. Tropical mathematics also provides appropriate mathematical language and tools for various other applications which willbe presented at the workshop.
The talks on mathematical optimisation in railway engineering will be given by Professor Clive Roberts and other prominent specialists working at the Birmingham Centre for Railway Research and Education (BCRRE). They will inform the workshop participants about the problems that are of actual interest for railways, and suggest efficient and practical methods of their solution.
For a glimpse of some of the category theory lurking in this subject, see:
- Simon Willerton, Project scheduling and copresheaves, The -Category Café.
Re: Tropical algebra and railway optimization
It is now over 10 years since the mathematics section on the university of Bangor was shut down. Some time before that I used to teach a course that pretended to be Operational Research (and it was that but not in the usual way) but I sneaked in stuff on the use of Petri nets and of timed discrete event systems. This latter stuff used some notes of lectures by Stephane Gaubert more or less following the course, that he mentions on his website. This involved an introduction to Max-plus and working with calculations in that algebra. I liked this because it showed the value of abstraction and analogy in a very applied setting. Yes and I gave examples from scheduling and train management systems. This is lovely mathematics! The material was approachable by students with a normal background of 2 years of linear algebra, etc. and seemed to go down well. It lead on to several students doing their third year project topic on related areas.
Of course, I tried to hint at the categorical aspects of the topic and also the link with logics of various types. Most of the students had also taken a course in Finite Automata which helped in the way of thinking of them as a related example of this way of thinking uses ideas from Language theory. For that one replaces Max-plus by a related idempotent semi-ring. (And some of you will be thinking Quantales, and of course those are closely related to this stuff.)
As applied categorical theory (or almost) this tropical stuff is very topical stuff, but it is also very nice to teach and fun to do (and if kept at the elementary level does not require that much background). Another useful link is this page.
I have tried on several occasions to suggest this area as being ripe for a categorical approach and the Compositionality idea and Applied Category theory course that John is running should enable that idea finally to get started. It was one of several applied areas that I had hoped to continue when our department was shut down.