The max-plus algebra, or tropical semiring, is the rig based on the set of real numbers extended by $-\infty$ (the upper reals), with addition $x \oplus y = max(x,y)$ and multiplication $x \otimes y = x + y$. Similarly, the min-plus algebra, or rig of costs, is the rig based on the set of real numbers extended by $\infty$ (the lower reals), with addition $x \oplus y = min(x,y)$ and multiplication $x \otimes y = x + y$. The two rigs are isomorphic, with an isomorphism (either way) given by $x \mapsto -x$; the difference is just a matter of the desired perspective.

Applications

The max-plus algebra is an idempotent semiring and dioid that is used in the modelling of timed systems. Typically in a simple example, the completion time of a production system will be given by a system of equations that have ‘max’ occurring in them. (The next process in a system cannot start until all its component parts have been themselves completed.) The use of the max-plus notation completely linearises many systems.

There are several research groups, world wide, with research in this area and with good websites, including simulation, and calculational, tools. One way into the network of these sites is here.

Last revised on September 4, 2011 at 11:47:33.
See the history of this page for a list of all contributions to it.