1 Solving two-sided (max,plus)-linear equation systems.

By Karel Zimmermann.

Systems of equations of the following form will be considered:

a_{i}(x) = b_{i}(x) i ∈ I,  (1)

where I = {1, …, m}, J = {1, …, m},

a_{i}(x) = max_{j∈J}(a_{ij} + x_{j}), b_{i}(x) = max_{j∈J}(b_{ij} + x_{j}) ∀i ∈ I

and a_{ij}, b_{ij} are given real numbers. The aim of the contribution is to propose a polynomial method for solving system (??). Let M be the set of all solutions of (??), let M(\overline{x}) denote the set of solutions of system (??) satisfying the additional constraint x ≤ \overline{x}, where \overline{x} is a given fixed element of R^{n}. The proposed method either finds the maximum element of the set M(\overline{x}) (i.e. element x̂ ∈ M(\overline{x}), for which x ∈ M(\overline{x}) implies x ≤ x̂), or finds out that M(\overline{x}) = ∅. The results are based on the following properties of system (??) (to simplify the notations we will assume in the sequel w.l.o.g. that a_{i}(\overline{x}) ≥ b_{i}(\overline{x}) ∀ i ∈ I and \overline{x} ∉ M(\overline{x})):

(i) M(\overline{x}) = ∅ ⇒ M = ∅. (ii) Let K_{i} = {k ∈ J ; a_{ik} ≤ b_{ik}} ∀i ∈ I. If for some i_{0} ∈ I the set K_{i_{0}} = ∅, then M(\overline{x}) = ∅. (iii) Let β_{i}(\overline{x}) = max_{k∈K_{i}}(b_{ik} + \overline{x}_{k}), L_{i}(\overline{x}) = \{j ∈ J ; a_{ij} + \overline{x}_{j} > β_{i}(\overline{x})\}, ∀ i ∈ I. If ⋃_{i∈I} L_{i}(\overline{x}) = J, then M(\overline{x}) = ∅. (iv) Let V_{j}(\overline{x}) = \{i ∈ I; j ∈ L_{i}(\overline{x})\}, let \overline{x}_{j}^{(1)} = min_{i∈V_{j}(\overline{x})}(β_{i}(\overline{x}) − a_{ij}) for all j ∈ J, for which V_{j}(\overline{x}) ≠ ∅ and \overline{x}_{j}^{(1)} = \overline{x}_{j} otherwise. Let β_{i}(\overline{x}^{(1)}) < β_{i}(\overline{x}) for all i ∈ I. Then for at least one i ∈ I the value β_{i}(\overline{x}^{(1)}) is equal to at least one of the threshold values b_{ij} + \overline{x}_{j} < β_{i}(\overline{x}).

The method successively determines variables, which have to be decreased if equalities in (??) should be reached. If all variables have to be set in movement, no solution of (??) exists. If the set of unchanged variables is nonempty, the maximum element of (??) is obtained. Using these properties a polynomial behavior of the proposed method can be proved (in case of rational or integer inputs). Possibilities of further generalizations and usage in optimization with constraints (??), as well as applications to synchronization problems will be briefly discussed.