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

Lead Research Organisation:
University of Birmingham

Department Name: School of Mathematics

### Abstract

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.

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.

### 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 |