1 February 2008 - 30 April 2011
Max-algebra is a rapidly evolving branch of mathematics with potential to solve a class of non-linear problems in mathematics, science and engineering that can be given the form of linear problems, when arithmetical addition is replaced by the operation of maximum (or minimum) and arithmetical multiplication is replaced by addition. It was observed by researchers since the 1960’s that some non-linear problems can be formulated and analysed more easily when this notation is used. These included applications in the design of information processing technology and in the asynchronous processes of manufacturing. It appears that max-algebraic methodology is used in mathematical fields as different as control theory and algebraic geometry. Besides the advantage of dealing with non-linear problems as if they were linear the techniques of max-algebra enable us in some cases to efficiently describe the set of all solutions (where it is otherwise very difficult or even impossible to do so) and thus choose a best one with respect to a specified criterion. It also provides an algebraic encoding of a class of combinatorial and combinatorial optimisation problems.
Problems in this project find applications for instance (but not exclusively) in the modelling of multi-machine interactive production processes (MMIPP) in which machines (processors) work in cycles and the starting times of the machines in each cycle are determined solely by the work of other machines in the previous cycle. One of them is to find and prove an analytical solubility criterion for the two-sided max-linear systems. It is of great importance as the two-sided max-linear systems are used for modelling of synchronisation in MMIPP.
Another example is the generalised max-algebraic eigenvalue-eigenvector problem. This is considered to be one of the most difficult problems in max-algebra.
Special attention will be paid to the connections between max-algebraic and nonnegative matrix theory as there are striking similarities between the spectral theory of nonnegative matrices in linear algebra and spectral theory in max-algebra.
Max-linear programs with one-sided constraints are well known and relatively easy to solve. However, no method seems to exist for the two-sided case. So another aim is to solve the max-linear programming problem with two-sided linear constraints. This would be a major contribution to optimal synchronisation in MMIPP.
Another group of problems is related to reachability of a steady-state in MMIPP, that is a situation in which the lengths of cycles of all machines are equal and the system moves forward in regular steps. Partial answers are known, however, there is currently no method for solving this question in general.
Principal Investigator: Dr Peter Butkovic (School of Mathematics, University of Birmingham)
Research Fellow: Dr Sergei Sergeev (School of Mathematics, University of Birmingham)
Visiting Researcher: Professor Hans Schneider (Department of Mathematics, University of Wisconsin, Madison)
1. P. Butkovic: Max-linear Systems: Theory and Algorithms (Springer Monographs in Mathematics, Springer-Verlag 2010) Springerlink
2. P. Butkovic, R.A.Cuninghame-Green and S.Gaubert, Reducible spectral theory with applications to the robustness of matrices in max-algebra. SIAM Journal on Matrix Analysis and Applications 31(3) (2009) 1412-1431.
3. S. Sergeev and H. Schneider.CSR
expansions of matrix powers in max algebra. Trans. Amer. Math. Soc., 364, 2012, 5969-5994.
4. S. Sergeev, H.Schneider and P.Butkovic, On visualization scaling, subeigenvectors and Kleene stars in max algebra. Linear Algebra and its Applications 431 (2009) 2395–2406.
5. P.Butkovič and A. Aminu, Introduction to max-linear programming. IMA Journal of Management Mathematics.(2009) 20 (3): 233-249.
6. S. Sergeev, Max-algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes. Linear Algebra and its Applications 431 (2009) 1325–1339.
7. S. Sergeev, On cyclic classes and attraction cones in max algebra. University of Birmingham, School of Mathematics, Preprint 2009/05. E-print arXiv:0903.3960.
8. S. Sergeev. Universal algorithms for generalized discrete matrix Bellman equations with symmetric Toeplitz matrix. Tambov University Reports, ser. Natural and Technical Sciences, volume 16, issue 6, part 2, 2011, 1751-1758.
9. S. Sergeev, Idempotent convexity in finite-dimensional geometry. In: Mathematical Forum vol. 2, Proceedings in convex analysis (Isslesovania po vypuklomu analizu), Vladikavkaz (Russia), 2009, pages 225-229, in Russian.
10. S. Sergeev, Multiorder, Kleene Stars and Cyclic Projectors in the Geometry of Max Cones, In: G.L. Litvinov and S.N. Sergeev (Eds.) "Tropical and Idempotent Mathematics", volume 495 of Contemporary Mathematics, pages 317-342.
11. S. Sergeev, On the system Ax=lambda Bx in max algebra: every system of intervals is a spectrum, Kybernetika, Volume 47, no. 5, 715-721, 2011.
12. S. Sergeev: Max-algebraic attraction cones of nonnegative irreducible matrices Linear Algebra and its Applications 435 (2011) 1736-1757
13. V. Nitica and S. Sergeev. On hyperplanes and semispaces in max-min convex geometry, Kybernetika, Vol. 46 (3) (2010) 552-561.
14. V. Nitica and S. Sergeev. An interval version of separation by semispaces in max-min convexity Linear Algebra and its Applications 435 (2011) 1637-1648
15. R.D. Katz, H. Schneider and S. Sergeev, On commuting matrices in max algebra and in classical nonnegative algebra. Linear Algebra and its Applications 436 (2012) 276-292.
16. S.Gaubert and S.Sergeev, Cyclic projectors and separation theorems in idempotent convex geometry. J. of Mathematical Sciences, Vol. 155 (6) (2008) 815-829.
17. S.Sergeev and E.Wagneur, Basic solutions of systems with two max-linear inequalities Linear Algebra and its Applications 435 (2011) 1758-1768
18. S. Gaubert, R.D. Katz and S. Sergeev, Tropical linear-fractional programming and parametric mean-payoff games, Journal of Symbolic Computation 47 (2012) 1447–1478
19. S. Sergeev, Mean-payoff games and parametric tropical two-sided systems, University of Birmingham, University of Birmingham, School of Mathematics, Preprint 2010/15.
20. R.A.Cuninghame-Green and P.Butkovic, Generalised eigenproblem in max algebra, IEEE Xplore, Discrete Event Systems (2008), 9th International Workshop WODES 2008, 236-241, http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4605951&isnumber=4605912.
21. P.Butkovic, Finding a bounded mixed-integer solution to a system of dual inequalities, Operations Research Letters 36 (2008) 623-627.
22. P.Butkovic, Permuted max-algebraic (tropical) eigenvector problem is NP-complete. Linear Algebra and its Applications 428 (2008) 1874-1882.
23. P.Butkovic, Narrowing the search for eigenvalues in the generalised eigenproblem in max-algebra, The University of Birmingham, preprint 2008/25.
24. P.Butkovič and K.P.Tam, On some properties of the image set of a max-linear mapping, Contemporary Mathematics Series, AMS Providence, 495 (2009) 115-126.
25. A. Aminu and P.Butkovič: Non-linear programs with max-linear constraints: A heuristic approach, IMA Journal of Management Mathematics 2011; doi: 10.1093/imaman/dpq020.
26. A. Aminu and P.Butkovič, Comparison of methods for solving two-sided systems in max-algebra, The University of Birmingham, preprint 2008/08.
27. P.Butkovic and M.Fiedler: Tropical tensor product, The University of Birmingham, preprint 2011/02 .