Tropical Optimisation

Tropical mathematics is a relatively new branch of mathematics (initiated in the 1960's) where the usual set of arithmetical operations (+,*) is replaced with the tropical arithmetics in which the role of addition is played by the operation of taking maximum or minimum of two numbers. This appears to be useful in a number of problems which are non-linear in the sense of "traditional" mathematics, but can be seen as linear over the tropical arithmetics. In particular, the whole Dutch railway network has been recently modelled as a huge tropical linear system, where the tools of tropical algebra can be exploited in order to evaluate viability and stability of the network and to visualise the propagation of delays. On the theoretical side, the development of tropical mathematics has been driven by search for analogies of useful facts, concepts and constructions of "traditional" mathematics.

The theme of the project is tropical optimisation. In principle, optimisation is one of the most applicable branches of mathematics. An ordinary person is solving various optimisation problems every day, for example, to minimise time and money that they spend or to maximise the impact of their effort. Mathematical formulation of an optimisation problem typically consists of an objective function to be optimised and a mathematical description of the area and variables over which the optimisation is performed. The project is focused, more specifically, on the case when both the function to be optimised and the optimisation domain can be most conveniently described in terms of tropical algebra.

We will solve problems of optimal control with switching tropical linear systems. In terms of railway scheduling applications that will mean optimising dispatchers' decisions in order to minimise the cumulative or maximal delays of train departures, thus responding to the public demand to increase the punctuality of railway operations. Since our approach will be rooted in tropical algebraic theory, new solutions to tropical optimal control problems will create new synergies between railway engineering and tropical mathematics communities.

We will also solve tropical pseudo-quadratic programming and bilevel programming problems. Solutions of these problems will be further applied to project scheduling and urban planning problems with various synchronisation requirements. Let us point out here that bilevel optimisation has numerous applications in logistics and economics, since it handles real life situations which can be modelled as games between the leader and several followers who adjust their actions depending on the leader's policies but whose decisions might also influence leader's income. Solving the tropical analogues of these problems will enable us to deal with such situations also in the areas where the tropical optimisation is applied.

The proposed research is going to develop the theory and algorithms of tropical optimisation. This is an emerging mathematical field on the interface of linear and nonlinear optimisation, convex geometry, combinatorics, tropical linear algebra, and with various applications in planning and scheduling (railway scheduling, project scheduling, urban planning). Therefore a successful project in tropical optimisation will result both in academic impact (new connections between researchers from different areas, new collaboration and projects) and in industrial impact related to the areas of application, as outlined below:

1. Tropical pseudoquadratic programming.
Optimal scheduling is a vast area, where various real-life scheduling problems and their algorithmic solutions are studied. Tropical optimisation will enrich this area with new problem formulations as well as solution approaches. In some cases it will provide a closed-form description of the full solution set, and with the tropical mathematics approach we will solve new types of optimal scheduling problems for several projects that have to be synchronized.
In urban planning, tropical pseudoquadratic programming can be applied to minimax location problems. Application of tropical optimisation methods in this area will result in new theory and efficient description of solutions to such problems. This will contribute to more efficient handling of urban planning problems in practice.

2. Tropical bilevel programming.
In the area of optimal scheduling, tropical bilevel programming can model a situation where there is one master project and several follower projects of several teams or factories. Followers would like to achieve their optimization goals (such as minimizing the greatest deviation of finish times or the greatest flow time), but their time constraints depend on the decisions of the master who would also like to optimize the timing of their master project. Same kind of applications can be considered also in urban planning: a minimax location problem to be solved by a central government and similar lower level location problems to be solved by local authorities.

3. Optimal Control for Switching Max-Plus systems.
Train traffic is often disturbed by delays, and then the propagation of delays along the network occurs. These delays are typically minimized or avoided by dispatchers, who can take appropriate decisions. This decision making determines the timetable resilience: the flexibility of a timetable to prevent or reduce secondary delays using rescheduling. In this project we are going to develop mathematical theory for tropical optimal control problems which is lacking at present. This theory will give rise to new algorithmic approaches to their solution. This is then going to aid the optimal decision making in railway scheduling, with the aim of reducing the total or maximal delay of all trains and thus addressing the public demand to increase the punctuality of railway operations.