Tropical Optimisation

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

Abstract

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.

Planned Impact

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.

Publications

10 25 50
 
Description Key Finding 1: Some new tropical pseudoquadratic optimization problems have been solved and their solution has been used in the development of a new tropical AHP decision method. This finding, obtained in collaboration with Nikolai Krivulin, was reported at UKSim-AMSS 11th European Modelling Symposium on Computer Modelling and Simulation (EMS 2017), 20-22 November 2017, Manchester, UK, and at 2nd IMA and OR Society Conference on Mathematics of Operations Research. A paper containing all details of the finding has been published in "Fuzzy Sets and Systems" journal (see publications). Also, solution of other kinds of tropical pseudo-linear and tropical pseudo-quadratic problems with general tropically linear constraints by means of mean-payoff game solvers has been described in arXiv preprint https://arxiv.org/abs/2009.12930 (submitted to a journal but not yet published).

Key Finding 2: A particular problem of tropical bilevel linear programming has been investigated and some solution methods for it have been constructed, in collaboration with my PDRA Zhengliang Liu. This finding has been reported at World Congress on Global Optimization (WCGO 2019). A paper on this has been published as a Chapter in a conference proceedings volume "Optimization of Complex Systems: Theory, Models, Algorithms and Applications, WCGO 2019, World Congress on Global Optimization, Metz, France, 8-10 July, 2019." (see publications)

Key Finding 3: Inhomogeneous products of tropical matrices have been studied, and a new bound on the factor-rank transient of such products has been established, meaning the bound after which such products admit a certain type of matrix factorisation. The details this finding can be seen in the new preprint that has been written with my PhD student Arthur Kennedy-Cochran-Patrick (https://arxiv.org/abs/2009.07804). An earlier paper, developed for more restrictive class of matrices and offering a bound for the rank-one transient, was written in collaboration with my PDRA Stefan Berezny and the same PhD student. It has been published in "Kybernetika" journal (see publications).

Key Finding 4: In collaboration with A. Niv and M. Maccaig, I developed an application of a formula of tropical linear algebra (called "tropical Jacobi identity") to optimal assignments with supervisions. This combinatorial optimisation problem, which (to our knowledge) was not considered previously, means optimally assigning multiple tasks to one team, or daily tasks to multiple teams, where each team has a supervisor task or a supervised task. We analysed the complexity of this problem, how the tropical Jacobi identity can be interpreted in terms of this problem and how it can help to solve it (in some special case). See publications.

I also obtained a number of new results in tropical linear algebra. In collaboration with Jan Plavka (Slovakia), I developed an interval extension of robustness for tropical circulant matrices. In the framework of this development we also studied basic properties of tropical circulant matrices and their attraction cones (see my publication with J. Plavka). In collaboration with Glenn Merlet and Thomas Nowak (France) and my PhD student Arthur Kennedy-Cochran-Patrick, I developed a number of new bounds on the periodicity transients of tropical matrix powers and described matrices which attain various bounds on the periodicity transients of tropical matrix powers (see two new publications with these authors). Also in collaboration with Martin Gavalec and Zuzana Nemcova, we developed a new theory of eigenvectors in max-min algebra (see my publication with these authors).
Exploitation Route The new tropical AHP method can be useful for Decision Makers as an alternative to the traditional AHP method developed by Saaty in 1970s. Unlike the traditional AHP method it comes up with a set of priority vectors, which is then represented, in some sense, by a vector which is the most differentiating and the least differentiating between the alternatives. The paper on tropical bilevel optimization is most probably the first work, which is extending the methods and approaches of bilevel optimization to tropical mathematics (Objective 2 of the grant). The study of inhomogenous matrix products, being a part of Objective 3 of the grant, is highly relevant to the study of tropical switching systems that model railway timetables and, e.g., legged locomotion of robots. Key Findings 1.-3. are also of academic interest to our colleagues in France, UK and the Netherlands, who are working in tropical optimization and tropical switching models. Besides that, the work on application of the tropical Jacobi identity can be useful to decision makers who have to assign teams to multiple tasks, and the work on the bounds for periodicity transients of tropical matrix powers is developing further one of the most classical research topics in tropical linear algebra. The results and methods of their proof are quite nontrivial and will inspire new problem formulations in Combinatorics. The research on circulant matrices is contributing to the study of special types of matrices as well as to Interval Analysis and can be of interest to specialists in these areas of mathematics. Finally, the work on max-min eigenvectors is fundamental for developing new applications of tropical linear algebra over the max-min (fuzzy) semiring.
Sectors Financial Services

and Management Consultancy

Transport

 
Description Collaboration with Dr. Adi Niv (Tel-Aviv, Israel) 
Organisation Kibbutzim College
Country Israel 
Sector Academic/University 
PI Contribution The article "Optimal assignments with supervisions": working out some of the main statements and proofs of the paper and adding new results on the computational complexity of the problem.
Collaborator Contribution The article "Optimal assignments with supervisions": the tropical Jacobi identity and the idea to describe the combinatorial optimisation problem that can be associated with it.
Impact The article "Optimal assignments with supervisions" has been written and published in a high-ranking journal. Our article describes a problem of combinatorial optimisation associated with the tropical Jacobi identity, which is an identity of tropical linear algebra, and explains how the tropical Jacobi identity helps to solve this problem in an important special case. The problem can be of interest to specialists in operational research, for example, in the situation when one has to find an optimal weekly plan of assigning workers to tasks given that some workers have to be supervised on some tasks every day.
Start Year 2017
 
Description Collaboration with Glenn Merlet (Marseille, France) and Thomas Nowak (Paris, France) 
Organisation Aix-Marseille University
Country France 
Sector Academic/University 
PI Contribution The award has helped to restart our collaboration with Dr. Glenn Merlet from Aix-Marseille University in France and with Dr. Thomas Nowak (Paris, France). We have created together two academic papers during the project duration, and they finally got published in the end of 2020 and beginning of 2021. The research also involved Arthur Kennedy-Cochran-Patrick (University of Birmingham). The contribution of all participants was fair and equal and included theoretical hypothesis, proofs and examples illustrating the validity and the sense of proven statements.
Collaborator Contribution The contribution of all participants was fair and equal and included theoretical hypothesis, proofs and examples illustrating the validity and the sense of proven statements.
Impact 1. Article "New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank" (coauthored by A. Kennedy-Cochran-Patrick, G. Merlet, T. Nowak and S. Sergeev, published in the journal "Linear Algebra and its Applications") offers new bounds on the periodicity transient of tropical matrix powers that make use of cyclicity of the ambient digraph and the factor rank. See https://www.sciencedirect.com/science/article/pii/S0024379520305152 2. Article "On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers" (coauthored by G. Merlet, T. Nowak and S. Sergeev, published in the journal "Linear and Multilinear Algebra) offers an in-depth analysis of matrices that precisely attain some bounds on the periodicity transient that were obtained earlier. See https://www.tandfonline.com/doi/abs/10.1080/03081087.2021.1878995
Start Year 2017
 
Description Collaboration with Prof. Nikolai Krivulin 
Organisation Saint Petersburg State University
Country Russian Federation 
Sector Academic/University 
PI Contribution I have contributed to the mathematical foundations of the method by 1) improving the result on a particular problem of tropical pseudoquadratic optimisation and 2) adding new geometric ideas on maximising and minimising the Hilbert seminorm. I have also organised the LMS Workshop on tropical mathematics where Prof. Krivulin presented our joint work, and funded from the current Award my visit to Saint Petersburg and his visit to Birmingham in May and November 2017, respectively.
Collaborator Contribution The idea of the new tropical AHP method came from Prof. Krivulin, as well as the basic methods of solving particular problems of the tropical pseudoquadratic optimisation.
Impact We have written a joint paper on new results in tropical optimization and a new tropical analogue of the AHP method based on these tropical optimization techniques. The paper has been published in the journal "Fuzzy Sets and Systems" (with a high ranking) and is also available as an arxiv preprint. The main findings in that paper have been reported at the LMS Workshop in Birmingham, the European Modelling Symposium in Manchester and 2nd IMA and OR society conference on mathematics of operational research (see Engagement Activities). See also http://uksim.info/ems2017/CD/data/1410a038.pdf for extended conference abstract at EMS.
Start Year 2017
 
Description Organizing an LMS workshop on tropical mathematics 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Professional Practitioners
Results and Impact In January 2019 I organized a workshop on tropical mathematics and its publications. The main purpose of organizing this event was to engage the tropical mathematics community in the UK with new results on connections between tropical mathematics and optimization achieved in collaboration with Dr. Adi Niv and by the team of Dr. S. Gaubert who was visiting me at the time. The workshop was attended by 25-30 people mostly from the UK (Birmingham, Manchester, London, Swansea and other places). Although most funding for the event came from LMS, current EPSRC grant money was used to fund the productive visits of Dr. A. Niv and Dr. S. Gaubert.
Year(s) Of Engagement Activity 2019
URL https://www.birmingham.ac.uk/schools/mathematics/news-and-events/events/2019/tropical-mathematics-ap...
 
Description Organizing an LMS workshop on tropical mathematics 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact In November 2017 I organized a workshop on tropical mathematics and its applications. A number of European researchers contributed to it by giving a talk, and my collaborator Prof. Nikolai Krivulin gave a talk on our joint research in tropical optimization and described the tropical analogue of the AHP method for ranking alternatives which we have developed. The workshop took place in School of Mathematics, University of Birmingham and was attended by about 25-30 researchers from the UK, Europe and Russia. Although it was funded by LMS and not by the current award, I feel that it is worth mentioning it here as it contributed to the dissemination of the research on Tropical Optimization.
Year(s) Of Engagement Activity 2017
URL https://www.birmingham.ac.uk/schools/mathematics/news-and-events/events/2017/tropical-mathematics-ap...
 
Description Participation in European Modelling Symposium (Manchester, November 2017) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Me and my collaborator Prof. Krivulin attended a European Modelling Symposium in Manchester, in November 2017. The audience of that symposium was quite diverse: a collection of researchers from all branches of applied science and industry, presenting applications ranging from computer engineering to design of fuel cells and speech recognition. Our primary purpose was to engage those specialists with our research and try to foster new unexpected contacts and collaborations. A short paper describing the new tropical AHP method is going to be published by IEEE Conference Publication Services.
Year(s) Of Engagement Activity 2017
URL http://ems2017.info/
 
Description Talk at 2nd IMA and OR society conference on mathematics of operational research 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact The conference took place in the end of April 2019 in Aston University (Birmingham). It attracted many excellent specialists in Operational Research from UK and Europe. The keynote speakers were such renowned practitioners and experts in Operational Research as J. Bradley (Royal Mail), S. Henderson (Cornell), S. Leyffer ((Argonne), V. Pope (Met Office), R. Solly (DSTL) and M. Vojnovic (LSE). My purpose was to give a talk on the new Tropical AHP method for decision-making, which we developed with N. Krivulin (see Publications).
Year(s) Of Engagement Activity 2019
URL https://cdn.ima.org.uk/wp/wp-content/uploads/2018/06/PROGRAMME-INSERT.pdf
 
Description Talk at Conference "WCGO-19" 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact In July 2019, I took part in World Congress on Global Optimization, organized by the International Society of Global Optimization. The conference brought together many of the world's leading experts in nonconvex programming and global optimization, with plenary talks given by P. Pardalos, A. Nagurney, A. Zhigljavsky, A. Ben-Tal, M. Fukushima, I.M. Bomze and S. Butenko, and parallel sessions on optimization methods under uncertainty, machine learning and big data, network optimisation and multiobjective programming, to mention a few. My purpose was to disseminate my research on bi-level programming, done in collaboration with one of my research fellows (Z. Liu). After my talk, several people from the audience told me that my research was very interesting to them and they would like to learn more about tropical optimisation in the future.
Year(s) Of Engagement Activity 2019
URL https://wcgo2019.event.univ-lorraine.fr/page/program_page
 
Description Talk at International Linear Algebra and Matrix Theory Workshop at University College Dublin 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact International Linear Algebra Conference in UCD took place in the end of May 2019. It attracted such renowned experts in Linear Algebra and Numerical Algorithms as C. Johnson, V. Mehrmann, T. Laffey and H. Smigoc. I was invited to give a talk on tropical matrix algebra. My talk was on the ongoing work on tropical matrix powers and their periodicity transients, with extension to non-homogenous matrix products, which I am doing jointly with my colleagues in France (G. Merlet and T. Nowak) and my PhD student A. Kennedy-Cochran-Patrick. As a result of my talk, the audience became more interested in tropical matrix algebra and in tropical matrix powers in particular.
Year(s) Of Engagement Activity 2019
URL https://maths.ucd.ie/lamt/Abstracts.pdf
 
Description Talk on tropical bilevel optimisation (ONA Seminar at University of Birmingham) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Professional Practitioners
Results and Impact In November 2017 I gave a talk on a problem of tropical bilevel optimisation and solution methods for it. The main purpose of the talk was to engage the specialists in optimisation with the research problems and findings associated with this Grant.
Year(s) Of Engagement Activity 2017
URL http://talks.bham.ac.uk/talk/index/2915
 
Description Tropical Mathematics and Optimization for Railways 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact The main purpose of the one-day workshop was to bring together specialists in tropical mathematics and mathematical optimisation applied in railway engineering and to foster further collaboration between them. The workshop featured talks by: 1) railway engineers and researchers from BCRRE (University of Birmingham) and TU Delft (the Netherlands),
2) specialists in mathematical optimisation and tropical mathematics (University of Birmingham, University of Bath, INRIA and TU Delft). The workshop inspired some further questions and discussion about joint research and, in particular, joint PhD projects between BCRRE and School of Mathematics of University of Birmingham and TU Delft.
Year(s) Of Engagement Activity 2018
URL https://www.birmingham.ac.uk/schools/mathematics/news-and-events/events/2018/tropical-mathematics-op...