It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 500
- Study Groups 19
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 68
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 713

Options

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

- Tropical Mathematics & Optimisation for Railways, University of Birmingham, School of Engineering, Monday 18 June 2018.

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 "ri**n**g without **n**egatives".

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 n-Category Café*.

## Comments

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.

`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.`

Yes, that'd be interesting!

I've updated my article here.

`Yes, that'd be interesting! I've updated my article here.`

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!

`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!`

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

`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`

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:

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

whyneural nets generalize to unseen data so well in practical terms, so this paper is a good stab on thinking about what happens.`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.`

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

Will somebody please explain how this can be true?

`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?`

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.

`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).`

Thanks for the link which exposes my problem:

`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.`

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 (?).

`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 (?).`