# Feasibility and reachability in max-linear systems

Lead Research Organisation:
University of Birmingham

Department Name: School of Mathematics

### Abstract

Max-algebra is a mathematical theory which uses algebra and combinatorics to provide powerful modelling and solution techniques for dealing with a range of managerial problems. The key feature of max-algebra is the possibility of solving non-linear problems in a linear-like way. It was observed by several researchers in the 1960-70's that some non-linear problems can be formulated and analysed more easily when the conventional addition is replaced by the operation of maximum and conventional multiplication is replaced by addition. The interest in this type of system arose from several sources. For example, in some asynchronous processes of production of information technology, in manufacturing and elsewhere, an appropriate mathematical description is obtained when the underlying scalar algebra is max-algebra. On the other hand, it appears that mathematical applications of max-algebra range between fields as different as control theory and algebraic geometry.The problems in this research proposal 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. Following the recent research breakthrough (co-authored by the Principal Investigator) in the 30-year open problem of solving two-sided max-linear systems by finding a strongly polynomial method, the stepping stone algorithm (SSA), in the proposed research we intend to solve a number of related open problems. One of them is to find and prove an analytical solubility criterion for the two-sided max-linear systems. This is a challenging task as attempts to find such criteria in the past have failed. 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. Recently a solution method for one very limited special case has been announced. Together with the SSA this opens the possibility of a breakthrough in the generalized max-algebraic eigenvalue-eigenvector problem. Special attention will be paid to the connections between max-algebraic and nonnegative matrix theory as there are striking similarities and some differences 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 the next 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.It is proposed that a Research Assistant and a Visiting Researcher are involved in this research. Together with the Principal Investigator they would generate and prove or disprove conjectures and produce theory and methods for solving the above mentioned open problems.The proposed Visiting Researcher is Prof. H.Schneider (University of Wisconsin, Madison), one of the most famous linear algebraists who has previously collaborated with the Principal Investigator. All significant results achieved during the proposed research would be published in academic journals and presented at international conferences and/or seminars. The final report for this project will also appear on the Principal Investigator's website.

### Organisations

## People |
## ORCID iD |

Peter Butkovic (Principal Investigator) |

### Publications

Aminu A
(2011)

*Non-linear programs with max-linear constraints: a heuristic approach*in IMA Journal of Management Mathematics
Butkovic P
(2008)

*Permuted max-algebraic eigenvector problem is NP-complete*in Linear Algebra and its Applications
Butkovic P
(2009)

*Tropical and Idempotent Mathematics*
Butkovic P
(2010)

*Reducible Spectral Theory with Applications to the Robustness of Matrices in Max-Algebra*in SIAM Journal on Matrix Analysis and Applications
Butkovic P
(2008)

*Introduction to max-linear programming*in IMA Journal of Management Mathematics
Butkovic P
(2008)

*Finding a bounded mixed-integer solution to a system of dual network inequalities*in Operations Research Letters
Butkovic, P.
(2010)

*Max-linear Systems: Theory and Algorithms*
Cuninghame-Green R
(2008)

*Generalised eigenproblem in max-algebra*
Gaubert S
(2012)

*Tropical linear-fractional programming and parametric mean payoff games*in Journal of Symbolic Computation
Gaubert S
(2008)

*Cyclic projectors and separation theorems in idempotent convex geometry*in Journal of Mathematical SciencesDescription | 1. One of the main problems studied in this project was the question of reachability of eigenspaces by matrix orbits. In applications this question corresponds to reachability of a steady regime in multiprocessor interactive systems which are linked to scheduling problems in manufacturing and transportation. Three fundamental questions of the reachability problem have been fully solved. One of them is the case when the orbit of the matrix reaches an eigenvector with any non-trivial starting vector (the production matrix is called strongly stable or robust), another one is when the orbit never reaches an eigenvector unless it starts in one (weakly stable matrices - this is a new concept not known at the time of the grant application). These two types are now fully and efficiently characterised for both irreducible and reducible matrices. The third question is an efficient algorithm for deciding whether an eigenvector of an irreducible matrix is reached by a given matrix orbit of this matrix. This result was generalised to eigenvectors of any power of the matrix. 2. It has been known for some time that the max-algebraic powers of irreducible matrices always reach a periodic regime after a finite number of steps. As an unexpected result a so called CSR representation of matrix powers was discovered. This result confirms the intuition that the dynamics of max-algebraic matrix powers is essentially controlled by the powers of Boolean matrices. This finding is likely to have groundbreaking implications for a range of hard problems such as the tropical roots of matrices and other tropical matrix functions. 3. Remarkable spectral properties of commuting matrices, in particular the existence of common eigenvalues, and the impact of these properties on commuting Boolean matrices have been discovered. 4. Full description of visualisation scaling, which emerges as a new and powerful tool in tropical linear algebra and highlights the role of subeigenvectors and Kleene stars. Visualisation scaling was developed in this project as a tool for solving the reachability problem (see point 1. above) and in the analysis of commuting matrices. It is now clear that it will also be useful as an important tool for solving a range of problems in tropical linear algebra. 5. The idea of visualisation was also instrumental for the description of attraction spaces (that is subspaces of starting vectors from which the orbit reaches an eigenspace) for irreducible matrices, using max-linear systems of equations. 6. Theory and algorithms for solving max-linear programs subject to one or two-sided max-linear constraints (both with minimisation and maximisation) have been developed and a seminal paper on max-linear programming has been published. This new methodology is based on the alternating method for solving two-sided systems and includes criteria for the objective function to be bounded and the proof that the finite bounds are always attained, if they exist. Also, bisection methods for localizing the optimal value with a given precision have been proved. For programs with integer entries these methods turn out to be exact, of pseudopolynomial computational complexity. |

Exploitation Route | The results of this project may be useful in solving a type of scheduling problems of manufacturing and transportation or to determine whether a stable regime of multiprocessor interactive systems will be reached in a finite number of steps. The results of this project will be useful for researchers in tropical linear algebra and its applications. They may also be useful in solving certain scheduling problems of manufacturing and transportation or to determine whether a stable regime of multiprocessor interactive systems will be reached in a finite number of steps. |

Sectors | Digital/Communication/Information Technologies (including Software) Manufacturing including Industrial Biotechology Transport |

URL | http://web.mat.bham.ac.uk/P.Butkovic/Grant.html |

Description | London Mathematical Society |

Amount | £3,600 (GBP) |

Funding ID | 31001-3 |

Organisation | London Mathematical Society |

Sector | Academic/University |

Country | United Kingdom |

Start | 09/2010 |

End | 07/2013 |