The same procedure as last year: The ATMOS deadline is approaching fast! It’s this Saturday, 24th June. Let’s hope there will be a small extension again.
The opportunities to travel and visit collaborators is surely one of the nicer aspects of our work in academia. And few would say No to an invitation to give a seminar talk in Montpellier. I certainly didn’t.
The University of Montpellier, founded in 1160, is one of the oldest in the world and is now home to some excellent research, in particular in robust optimisation. We are currently working on the concept of K-adaptability, where the decision maker selects a set of solutions with fixed cardinality, and once the scenario is revealed, he/she can choose one of the solutions from the set. These problems are more general than classic min-max approaches, but more restrictive than what is done in adjustable robustness.
It’s unfortunate if there is a call deadline at the same time – but now our application for a Newton Fund Institutional Link grant with Indonesian partners for disaster management has been submitted.
Last week I went to the “Mini-Workshop on Integrated Timetabling” in Göttingen, though I wonder if “mini” is the appropriate name for a three-day event? We enjoyed excellent talks on various combinations of timetabling with other problems in public transport. My own presentation was on “A New Robust Local Search Method and its Application to Uncertain Timetabling“, with the abstract below:
Railway timetabling problems are challenging to solve, even if all problem parameters are known exactly. If travel times are uncertain, as is the case in practice, finding good solutions is even harder.
I introduce a new local search technique to find robust solutions under implementation errors. In this setting, not the problem parameters are considered uncertain, but the actual implementation of a solution has an error margin. I first discuss an existing general approach to this problem by Bertsimas, Nohadani and Teo. I then introduce a new approach that is able to overcome local optima, and discuss its application to the train timetabling problem. While this is still work in progress, some first experimental results are presented.
I then went on to Osnabrück and gave a seminar talk on robust selection problems.
A lot has been written about solving robust problems when one knows exactly what the set of possible parameter realisations looks like. With the variable-sized robustness approach we have considered an alternative setting, in which the size of uncertainty is not really known. Still, we assume that the shape is given.
In a recent paper with the title “An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems”, we go back another step and evaluate which uncertainty sets actually make sense for shortest path problems. We use actual real-world traffic data to generate uncertainty sets and compare the performance of the resulting solutions. It turns out that hardness of the robust problem is not really an indicator for the usefulness of the resulting paths. See for yourself!
Through the development of efficient algorithms, data structures and preprocessing techniques, real-world shortest path problems in street networks are now very fast to solve. But in reality, the exact travel times along each arc in the network may not be known. This lead to the development of robust shortest path problems, where all possible arc travel times are contained in a so-called uncertainty set of possible outcomes.
Research in robust shortest path problems typically assumes this set to be given, and provides complexity results as well as algorithms depending on its shape. However, what can actually be observed in real-world problems are only discrete raw data points. The shape of the uncertainty is already a modelling assumption. In this paper we test several of the most widely used assumptions on the uncertainty set using real-world traffic measurements provided by the City of Chicago. We calculate the resulting different robust solutions, and evaluate which uncertainty approach is actually reasonable for our data. This anchors theoretical research in a real-world application and allows us to point out which robust models should be the future focus of algorithmic development.
Last week I returned to Birmingham’s Aston University (having been there in March to talk about optimisation methods in evacuation planning) and joined the first-of-its-kind IMA and OR Society Conference on Mathematics of Operational Research. That’s kind of awkward name for a great idea. The IMA, that is the Institute of mathematics and its applications, a society for the promotion of mathematical culture, and the OR Society have plenty of things in common, and organising a joint conference seems quite natural in hindsight. I’ve been to few other conferences where I enjoyed every single talk.
I used the opportunity to talk about variable-sized robustness, which has become an area of great interest for me recently. The basic idea, as we explored it over two papers (1,2), is that uncertainty sets in robust optimisation are typically not known to the decision maker. Usually only raw data is available, and a suitable uncertainty set needs to be determined before any robust model can actually start its work. In variable-sized robustness, we assume that only the desired shape of the set is known, but not its size. This leads to some new and challenging optimisation problems with close ties to multi-objecitve optimisation.
The IMA/OR conference was well attended and we can only hope to see more events of the same kind in the future!
February is nearly over, so let’s have a look what has happened:
- We sumitted a bid to the SEA2017 conference, titled “A New Perspective on Complexity for Robust Combinatorial Optimization”. Let’s see how it fares, it is a competitive venue. Our basic idea is quite nice, though: Do robust problems really get harder and harder, the more scenarios you add? Spoiler alert: Not quite!
- I wrote a grant proposal along similar lines, which is all ready for submission. Only some letters of support are still missing before I can send it on its way.
- The Mitteilungen der DMV is the magazine of the German Mathematical Society. I wrote an article about Brexit and its impact on my academic work, which will be in the next issue.
- In two weeks I will give a talk at the Midlands OR Society on optimisation methods for evacuation planning.
- And last but not least, I am now affiliated with the Data Science Institute at Lancaster University!