Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

May 24, 2018

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:

If you can go, please do — and report back!

Let me explain why it’s so cool…

Tropical algebra involves the numbers latex(,]latex (-\infty, \infty] 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:

Posted at May 24, 2018 10:39 PM UTC

TrackBack URL for this Entry:

5 Comments & 0 Trackbacks

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.

Posted by: Tim Porter on May 25, 2018 7:09 AM | Permalink | Reply to this

Re: Tropical algebra and railway optimization

I forgot to say that Max-plus is like the algebra John mentions but with min replaced by max and various minor adjustments made due to that change.

Posted by: Tim Porter on May 25, 2018 7:13 AM | Permalink | Reply to this

Re: Tropical algebra and railway optimization

It is now over 10 years since the mathematics section on the university of Bangor was shut down

Yes its still shut down:

And indeed -why would Britain need railway optimization? From the website:

British Rail operated the majority of the UK’s rail network between 1948 and 1997 under the ownership of the UK government. Originally British Rail was the merging of four separate companies. Known at the time as the “Big Four”, these companies were called:

London, Midland and Scottish Railway (LMS) London and North Eastern Railway (now London North Eastern Railway) Great Western Railway (GWR) Southern Railway (SR)

GWR is still in operation today and operated under franchise by FirstGroup.

Through a gradual period of nationalisation, much of the network was transformed into diesel and lines upgraded to incorporate electrification. This process saw the steam train become replaced completely by 1968 by diesel or electric locomotives. When it comes to innovation and train development during this time, the jewel in the crown for British Rail was the Inter-City 125 trains, or as it later became more commonly known as the ‘High-Speed Train’. There was one exception to the rule, a single narrow-gauge tourist line in Wales which to this day continues to operate under private ownership. As a leading heritage railway find out more about the Vale of Rheidol Railway here.

Posted by: nad on May 25, 2018 8:33 AM | Permalink | Reply to this

Re: Tropical algebra and railway optimization

Anything has to be better than the current methodology - Meltdown Monday.

Posted by: David Corfield on May 25, 2018 10:46 AM | Permalink | Reply to this

Re: Tropical algebra and railway optimization

Thanks - I hadn’t realized that railway timetables were a hot topic in the UK these days. The headline of an article published on the Sunday before “Meltdown Monday”:

Rail timetables overhaul aims to boost frequency and reliability


Now is the perfect time for a workshop on tropical geometry and railway timetable optimization… though I suspect it’s not just lack of mathematics that’s the problem now.

Posted by: John Baez on May 25, 2018 6:01 PM | Permalink | Reply to this

Post a New Comment