Feasibility and reachability in max-linear systems

极大代数是一种数学理论，它使用代数和组合学为处理一系列管理问题提供强大的建模和求解技术。极大代数的关键特征是能够以类线性的方式解决非线性问题。20世纪60-70年代的S等人观察到，用极大值运算代替传统的加法，用加法代替传统的乘法，可以更容易地对一些非线性问题进行表述和分析。对这种类型的系统的兴趣来自几个来源。例如，在信息技术生产的一些异步过程中，在制造业和其他地方，当基础标量代数是极大代数时，得到适当的数学描述。另一方面，极大代数的数学应用似乎在控制理论和代数几何等不同的领域中都有不同的应用。本研究方案中的问题在多机交互生产过程(MMIPP)的建模中得到应用，其中机器(处理器)循环工作，并且每个循环中机器的开始时间仅由前一循环中其他机器的工作来决定。在最近通过寻找强多项式方法-踏脚石算法(SSA)来解决双边极大线性方程组的30年来的公开问题方面取得了突破(与首席研究员共同撰写)，在拟议的研究中，我们打算解决一些相关的公开问题。其中之一是找到并证明了双边极大线性系统的解析可解性判据。这是一项具有挑战性的任务，因为过去试图找到这样的标准都失败了。在MMIPP中，采用双边极大线性系统进行同步建模，具有重要意义。另一个例子是广义极大代数特征值-特征向量问题。这被认为是极大代数中最困难的问题之一。最近公布了一个非常有限的特殊情况的解决方法。与SSA一起，这为广义极大代数特征值-特征向量问题提供了突破的可能性。由于线性代数中非负矩阵的谱理论与极大代数中的谱理论既有显著的相似之处，又有一些不同之处，本文将特别关注极大代数和非负矩阵理论之间的联系。带单边约束的极大线性规划是众所周知的，并且相对容易求解。然而，似乎没有一种方法可以解决这种两面性的情况。因此，下一个目标是解决带双边线性约束的极大线性规划问题。这将是对MMIPP中最优同步的主要贡献。另一组问题与MMIPP中稳态的可达性有关，即所有机器的周期长度相等并且系统以规则的步长前进的情况。部分答案是已知的，但目前还没有普遍解决这个问题的方法。建议由一名研究助理和一名访问研究员参与这项研究。他们将与首席调查员一起产生和证明或反驳猜想，并产生解决上述公开问题的理论和方法。建议的访问研究员是H·施奈德教授(威斯康星大学麦迪逊分校)，他是最著名的线性代数学家之一，曾与首席调查员合作。在拟议研究期间取得的所有重要成果将在学术期刊上发表，并在国际会议和/或研讨会上介绍。该项目的最后报告也将刊登在首席调查员的网站上。

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.