Feasibility and reachability in max-linear systems

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.