The (max,+) algebra (also known as max-plus algebra) redefines the operators plus and times from classical algebra as operators maximum (symbolized by ⨁) and plus (symbolized by ⨂) in the domain of real numbers ℝ augmented by minus infinity -∞. The (min,+) algebra (min-plus algebra) redefines operators plus and times from classical algebra as operators minimum (symbolized by ⨁) and plus (symbolized by ⨂) in the domain of real numbers ℝ augmented by plus infinity +∞.

Matrix computation in this algebra has been taught since 1960 by J. Kuntzman in his theory of networks. It is used in numerous domains such as operations research (network theory), physics (quantization), probability theory (Cramér's transform), control theory (discrete event systems), computer science (automata theory, Petri nets), and mathematics (algebraic geometry). This algebra is also known as tropical algebra.

This MaxPlus.jl package is a Julia port of the ScicosLab (max,+) toolbox (no longer maintained), which provides functions for numerical computations in (max,+) algebra. This Julia toolbox extends the original toolbox by adding (min,+) algebra support.

You may also be interested in this Timed Petri Net and Timed Event Graph graphical editor, which can generate (max,+) matrices from timed event graphs.

• Julia 1.10 or later (LTS recommended). Older Julia version may suffer of invalid results!
• All Julia standard libraries: LinearAlgebra, SparseArrays, Printf (no external dependencies).

julia> ]
pkg> add MaxPlus

git clone https://github.com/Lecrapouille/MaxPlus.jl.git --depth=1
cd MaxPlus.jl
julia --project -e 'using Pkg; Pkg.instantiate()'

Then from the Julia REPL:

julia> ]
pkg> dev .

julia> using MaxPlus

julia> MP([1 2; 3 8]) .+ 5
2×2 (max,+) dense matrix:
  5   5
  5   8

The result is computed as:

[max(1, 5)  max(2, 5)
 max(3, 5)  max(8, 5)]

Note: In (max,+) algebra, + computes the maximum and * computes the sum. The .+ is the Julia element-wise addition operator (broadcasted maximum in (max,+) algebra).

julia> MI([1 2; 3 8])
2×2 (min,+) dense matrix:
  1   2
  3   8

• MP is an alias for Tropical{Max} (max-plus scalars)
• MI is an alias for ``Tropical{Min}` (min-plus scalars)

julia> using SparseArrays

julia> A = MP([3.0 7; 2 4])
julia> λ, v = mpeigen(sparse(A))
(MP[4.5, 4.5], MP[6.5, 4.0])

julia> A * v == λ[1] * v
true

The package also provides semihoward for semi-Markov Howard algorithm with time weights.

julia> S = MPSysLin(MP([1 2; 3 4]), MP([1; 1]), MP([1 1]))
julia> [S; S]  # Vertical composition (vcat)
julia> [S S]   # Horizontal composition (hcat)

Full documentation is available at: https://lecrapouille.github.io/MaxPlus.jl

Contents:

• Introduction and tutorials (French and English)
• API: (max,+) functions
• API: (min,+) functions
• API: Linear systems
• ScicosLab to MaxPlus.jl translation
• Running tests
• Bibliography

• TimedPetriNetEditor: A graphical editor for Timed Petri Nets and Event Graphs with (max,+) algebra integration.

To use MaxPlus matrices with Graphs.jl, convert to classical algebra first:

using Graphs, SimpleWeightedGraphs
A = MP([3.0 7; 2 4])
g = SimpleWeightedDiGraph(plustimes(A))  # Convert to Float64 matrix

Contributions are welcome! Feel free to:

• Report issues
• Submit pull requests
• Improve documentation
• Add tests

This project is licensed under the GPL-3.0 License.