Feasibility and reachability in max-linear systems

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

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.