×

Simultaneous solution of linear equations and inequalities in max-algebra. (English) Zbl 1222.15002

A max algebra is an analog of a linear algebra over \(\mathbb{R}\), where scalar addition and multiplication are defined as follows: \[ a\oplus b=\max(a,b); \;\;\;\;a\otimes b=a+b,\;\;\;a,b\in\mathbb{R}. \] The author considers a joint system of equations and inequalities \[ A\otimes x=b, \;\;C\otimes x\leq d, \tag{1} \] where \(A\in\mathbb{R}^{k\times n}\), \(C\in\mathbb{R}^{r\times n}\), \(b\in\mathbb{R}^k\), \(d\in\mathbb{R}^r\). Existence of solutions for each of these systems was characterized by K. Zimmermann [Extremalni algebra. CSAV 46, Praha (1976)], and the unique solution case was characterized in [P. Butkovič, Linear Algebra Appl. 367, 313–335 (2003; Zbl 1022.15017)].
In the present work a characterization is given for existence and uniqueness of solutions of the joint system (1).
An algorithm is presented that performs max-linear programming. Its complexity is determined.

MSC:

15A06 Linear equations (linear algebraic aspects)
15A39 Linear inequalities of matrices
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization

Citations:

Zbl 1022.15017
PDFBibTeX XMLCite
Full Text: EuDML Link

References:

[1] Aminu, A.: Max-algebraic Linear Systems and Programs. PhD Thesis, University of Birmingham 2009. · Zbl 1169.90396
[2] Bacelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, Chichester 1992. · Zbl 0824.93003
[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics, Springer-Verlag 2010. · Zbl 1202.15032 · doi:10.1007/978-1-84996-299-5
[4] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra & Appl. 367 (2003), 313-335. · Zbl 1022.15017 · doi:10.1016/S0024-3795(02)00655-9
[5] Butkovič, P., Aminu, A.: Introduction to Max-linear programming. IMA J. Management Math. 20 (2009), 3, 233-249. · Zbl 1169.90396 · doi:10.1093/imaman/dpn029
[6] Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom. mat. Obzor. 20 (1984), 203-215. · Zbl 0545.90101
[7] Cuninghame-Green, R. A.: Minimax Algebra (Lecture Notes in Econom. and Math. Systems 166). Springer, Berlin 1979. · Zbl 0399.90052
[8] Cuninghame-Green, R. A., Butkovič, P.: The equation \(A\otimes {x}=B\otimes {y}\) over \((\max ,+)\). Theoret. Comput. Sci. 293 (1991), 3-12. · Zbl 1021.65022
[9] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-plus at work, Modelling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications. Princeton University Press, New Jersey 2006. · Zbl 1130.93003
[10] Vorobyov, N. N.: Extremal algebra of positive matrices (in Russian). Elektron. Datenverarbeitung Kybernet. 3 (1967), 39-71.
[11] Walkup, E. A., Boriello, G.: A general linear max-plus solution technique. Idempotency (Gunawardena, Cambridge University Press 1988, pp. 406-415.
[12] Zimmermann, K.: Extremální algebra (in Czech). Výzkumná publikace Ekonomicko-matematické laboratoře při Ekonomickém ústavu ČSAV, 46, Praha 1976.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.