Options

Tropical Algebra for Railway Optimization

Our discussion of PERT charts, \(\mathbf{Cost}\)-categories and the like is highly relevant to this workshop, which alas I cannot attend.

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

Tropical algebra involves the numbers \( (-\infty, \infty]\) made into a rig with minimization as the addition and addition as the multiplication. It's called a rig because it's a "ring without negatives".

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:

Comments

  • 1.

    It might be interesting to see how different scheduling problems behave. For instance, Job-shop scheduling is NP-hard, while certain instances of Flow shop scheduling are polynomial in complexity.

    Comment Source:It might be interesting to see how different scheduling problems behave. For instance, [Job-shop scheduling](https://en.wikipedia.org/wiki/Job_shop_scheduling) is NP-hard, while certain instances of [ Flow shop scheduling](https://en.wikipedia.org/wiki/Flow_shop_scheduling) are polynomial in complexity.
  • 2.

    Yes, that'd be interesting!

    I've updated my article here.

    Comment Source:Yes, that'd be interesting! I've updated my article here.
  • 3.

    John has cross posted this on the N-Cat Café and I have added a comment there that might be of use. This is lovely stuff to teach and my comment includes some links to notes that i used to use when I taught this in Bangor years ago. It is highly relevant to people interested in a categorical approach to problems and is great fun!

    Comment Source:John has cross posted this on the N-Cat Café and I have added a comment [there](https://golem.ph.utexas.edu/category/2018/05/tropical_mathematics_and_optim.html#more) that might be of use. This is lovely stuff to teach and my comment includes some links to notes that i used to use when I taught this in Bangor years ago. It is highly relevant to people interested in a categorical approach to problems and is great fun!
  • 4.
    edited May 25

    Thanks all for sharing very insteresting information and tips..I already did read some papers related (I guess) to this themes but in the communications frame like this :

    abstract

    We present an analytical framework for the delay analysis of the distributed coordinated scheduling in the IEEE 802.16 Wireless Network in mesh mode. We designed a queuing model that expresses the network limits accurately. The queuing model is of the type M/G/1/L developed using Linear Algebraic Queuing Theory. After modeling one node, an iterative method is used to calculate the traffic flowing in the whole network. With this model, it is possible to calculate the end-to-end delay and the throughput limit of the link layer. An algorithm is presented that applies a strategy to provide fair resource sharing. The numerical results and simulations for different topologies show that the model is accurate and that the fairness strategy effectively reduces the end-to-end delay

    https://dl.acm.org/citation.cfm?id=2564197

    best

    Comment Source:Thanks all for sharing very insteresting information and tips..I already did read some papers related (I guess) to this themes but in the communications frame like this : abstract We present an analytical framework for the delay analysis of the distributed coordinated scheduling in the IEEE 802.16 Wireless Network in mesh mode. We designed a queuing model that expresses the network limits accurately. The queuing model is of the type M/G/1/L developed using Linear Algebraic Queuing Theory. After modeling one node, an iterative method is used to calculate the traffic flowing in the whole network. With this model, it is possible to calculate the end-to-end delay and the throughput limit of the link layer. An algorithm is presented that applies a strategy to provide fair resource sharing. The numerical results and simulations for different topologies show that the model is accurate and that the fairness strategy effectively reduces the end-to-end delay https://dl.acm.org/citation.cfm?id=2564197 best
  • 5.
    edited June 11

    Last week or so it came out an interesting paper using Tropical Geometry helping to understand deep neural networks with ReLU activations. They show here this clean and elegant characterization:

    the family of functions represented by feedforward neural networks with rectified linear units and integer weights is exactly the family of tropical rational maps.

    As you know neural nets have had a shattering effect in industrial applications pushing state of the art boundaries in several machine learning problems and crossing the line separating curiosity from real utility in cases such as speech recognition task to name one.

    A classic neural net layer is a map between vector spaces consisting of an affine transformation given by free parameters (called weights) followed by a single, fixed-in-advance, element-wise nonlinearity. A net is a composition of layers. The nonlinearity acts isotropically conmuting with rotations but not translations, so the layers compose nontrivially. The net is used to aproximate an unknown map of which one only knows how it acts on a given set of poits (training set), and the goal is that the aproximation behaves similarly for formerly unknown points (test set). This is done by seeking the best combination of weights.

    As it happens, the exact nature of the choosen nonlinearity depends on pragmatic and technical factors as in this dicussion from practicioners. While traditionally a sigmoidal function (an exponential with saturation) was used by default, other options arise, and ReLU is a very simple one. The function is the double integral of the Dirac pulse, so always 0 until it starts to grow at constant speed. While the sigmoid is a trascendental function, the ReLU is much more cheaply computed so using it reduces training times and is one of the things being tried successfully in several tasks. Despite the practical success, there is consensus about the lack of understanding on why neural nets generalize to unseen data so well in practical terms, so this paper is a good stab on thinking about what happens.

    Comment Source:Last week or so it came out an interesting paper using Tropical Geometry helping to understand deep neural networks with ReLU activations. They show [here](https://arxiv.org/pdf/1805.07091.pdf) this clean and elegant characterization: > the family of functions represented by feedforward neural networks with rectified linear units and integer weights is exactly the family of tropical rational maps. As you know neural nets have had a shattering effect in industrial applications pushing state of the art boundaries in several machine learning problems and crossing the line separating curiosity from real utility in cases such as speech recognition task to name one. A classic neural net layer is a map between vector spaces consisting of an affine transformation given by free parameters (called weights) followed by a single, fixed-in-advance, element-wise nonlinearity. A net is a composition of layers. The nonlinearity acts isotropically conmuting with rotations but not translations, so the layers compose nontrivially. The net is used to aproximate an unknown map of which one only knows how it acts on a given set of poits (training set), and the goal is that the aproximation behaves similarly for formerly unknown points (test set). This is done by seeking the best combination of weights. As it happens, the exact nature of the choosen nonlinearity depends on pragmatic and technical factors as in this dicussion from [practicioners](https://www.reddit.com/r/MachineLearning/comments/73rtd7/d_do_you_still_use_relu_if_so_why/). While traditionally a sigmoidal function (an exponential with saturation) was used by default, other options arise, and ReLU is a very simple one. The function is the double integral of the Dirac pulse, so always 0 until it starts to grow at constant speed. While the sigmoid is a trascendental function, the ReLU is much more cheaply computed so using it reduces training times and is one of the things being tried successfully in several tasks. Despite the practical success, there is consensus about the lack of understanding on **why** neural nets generalize to unseen data so well in practical terms, so this paper is a good stab on thinking about what happens.
  • 6.

    Question. In Rau's paper page 11 they write:

    Clearly, the conventional linear order > on T = R ∪ {−∞} makes perfect sense tropically. Furthermore, we can express it in terms of tropical addition: we have a ≥ b if and only if “a + b” = b.

    Will somebody please explain how this can be true?

    Comment Source:Question. In [Rau's paper](https://www.math.uni-tuebingen.de/user/jora/downloads/main.pdf) page 11 they write: > Clearly, the conventional linear order > on T = R ∪ {−∞} makes perfect sense tropically. Furthermore, we can express it in terms of tropical addition: we have a ≥ b if and only if “a + b” = b. Will somebody please explain how this can be true?
  • 7.

    I haven't read that paper but tropically \(a+b\) means the \(max(a, b)\) we know and love, and that operation, understood as a semilattice has associated the usual order \(a \geq b \iff a \wedge b = b\), as in here.

    Comment Source:I haven't read that paper but tropically \\(a+b\\) means the \\(max(a, b)\\) we know and love, and that operation, understood as a semilattice has associated the usual order \\(a \geq b \iff a \wedge b = b\\), as in [here](https://en.wikipedia.org/wiki/Lattice_(order)#Connection_between_the_two_definitions).
  • 8.

    Thanks for the link which exposes my problem:

    A lattice element y is said to cover another element x, if y > x, but there does not exist a z such that y > z > x. Here, y > x means x ≤ y and x ≠ y.

    Comment Source:Thanks for the link which exposes my problem: > A lattice element y is said to cover another element x, if y > x, but there does not exist a z such that y > z > x. Here, y > x means x ≤ y and x ≠ y.
  • 9.
    edited June 11

    Hi Jim, mmh, thinking about your quote I'm not following what you meant: The order of the reals is dense so in the corresponding semilattice one element never covers the other (?).

    Comment Source:Hi Jim, mmh, thinking about your quote I'm not following what you meant: The order of the reals is dense so in the corresponding semilattice one element never covers the other (?).
Sign In or Register to comment.