Minplus

Minplus, or the min-plus algebra, is a mathematical framework used in optimization and scheduling that replaces the conventional addition and multiplication with the operations of taking minimum and addition. It is typically defined on the set R ∪ {+∞}, equipped with two binary operations: ⊕ (min) and ⊗ (ordinary addition).

Formally, for elements a, b in R ∪ {+∞}, a ⊕ b = min(a, b) and a ⊗ b = a + b. The semiring has additive identity +∞ because min(a, +∞) = a, and multiplicative identity 0 because a + 0 = a. The operation ⊕ is idempotent: a ⊕ a = a. The structure is associative and commutative for ⊕ and associative for ⊗, with ⊗ distributing over ⊕: a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c).

In matrix form, min-plus algebra defines matrix addition as componentwise minimum and matrix multiplication as the min-plus product: (A ⊗ B)_{ij} = min_k (A_{ik} + B_{kj}). This makes the min-plus semiring suitable for modeling path problems; the (min-plus) matrix product corresponds to concatenating paths and summing weights. The Kleene star A* = I ⊕ A ⊕ A^2 ⊕ ... yields the all-pairs shortest-path distances in a weighted graph, and algorithms like Floyd–Warshall operate naturally within this framework.

Min-plus algebra is a foundational tool in discrete-event systems, scheduling, network optimization, and control theory. It also appears in tropical geometry, where it provides a combinatorial shadow of algebraic varieties. A related framework is max-plus algebra, obtained by replacing ⊕ with max; the two are related by sign changes and are often viewed under the umbrella of tropical algebra.