Max-plus switching systems and long max-plus matrix products

Lead Research Organisation: University of Birmingham
Department Name: School of Mathematics


Switching max-plus linear (SMPL) systems are used to model the propagation of delays in a railway network.
Suppose that departure times of a network at a particular instant
are given by a vector x(k). The departure times at instant k are
given by a recurrence relation based upon the departure times at a
previous instant multiplied in the sense of max-plus arithmetic by
matrix A(u(k)) where u(k) is a control variable. At every instant, the network may
slightly change, which is encapsulated in this control variable.
This has a residual effect on the ultimate departure times, which
one often seeks to optimize in some way: for instance, by minimizing
the cumulative delay with respect to a given regular schedule.

The main idea of the proposed research is to study the switching
max-plus linear systems as vector orbits of a finitely generated max-plus matrix semigroup: the set of all
possible max-plus matrix products of a given finite set of matrices.

In this research we will be particularly interested in the long
max-plus matrix products and developing for them an analogue
of the CSR representation of max-plus matrix powers suggested by
Sergeev and Schneider. We then aim to apply the new theoretical
results which we obtain to switching max-plus systems and the above
mentioned optimization problems over them.


10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509590/1 01/10/2016 30/09/2021
1956719 Studentship EP/N509590/1 25/09/2017 31/03/2021 Arthur Kennedy-Cochran-Patrick
Description For a specific case of matrices we have developed a transient for a factor rank-one property of the long matrix product. This means that, using the specific type of matrices, if the length of the product (i.e. the number of matrices multiplied together) is greater than the transient, then the matrix can be written as the product of a column vector and row vector taken from the matrix.
Exploitation Route Primarily we aim to generalise the type of matrices used to allow a wider range of applications. As these are theoretical results there is also scope for applications of them in areas that require long max-plus matrix products.
Sectors Digital/Communication/Information Technologies (including Software),Transport