I am very happy to announce that some fruits of last year’s labour in Wroclaw are now ripe and ready. The paper is called “On Recoverable and Two-Stage Robust Selection Problems with Budgeted Uncertainty” and can be found here. The general idea is actually quite simple: Say we can choose p out of n items. Then the adversary can choose a bounded number of items and make them more expensive. Afterwards, in a third stage, we may exchange some of our items again. We tried to answer the question if this problem can be solved in polynomial time or not.
It turns out that this is indeed possible, if the uncertainty set is continuous. For discrete types of uncertainty, this question remains still open – but at least we found a way to formulate it as a compact mixed-integer programme. This is the abstract:
In this paper the problem of selecting p out of n available items is discussed, such that their total cost is minimized. We assume that costs are not known exactly, but stem from a set of possible outcomes.
Robust recoverable and two-stage models of this selection problem are analyzed. In the two-stage problem, up to p items is chosen in the first stage, and the solution is completed once the scenario becomes revealed in the second stage. In the recoverable problem, a set of p items is selected in the first stage, and can be modified by exchanging up to k items in the second stage, after a scenario reveals.
We assume that uncertain costs are modeled through bounded uncertainty sets, i.e., the interval uncertainty sets with an additional linear (budget) constraint, in their discrete and continuous variants. Polynomial algorithms for recoverable and two-stage selection problems with continuous bounded uncertainty, and compact mixed integer formulations in the case of discrete bounded uncertainty are constructed.
Next Friday (10 February) I will give a talk on the scenario aggregation results at the Combinatorial Optimization and Applications workshop in Edinburgh. The organisers were able to invite an impressive list of speakers, so I’m much looking forward to the packed single-day schedule!
We just uploaded a new preprint on approximation algorithms for min-max and min-max regret optimisation problems with discrete uncertainty sets.
For these kind of problems, there is a very simple method to find an approximation: If you are given K scenarios, take the average of them, and solve the resulting (much easier) problem. This gives a K-approximation for both min-max and min-max regret problems.
As easy as this method is, it still holds the title of being the best known approximation algorithm for a whole range of problems. Finally, our results make some progress in this regard: We show that it is possible to improve the K-approximation to an εK-approximation for any fixed ε.
The basic idea of our approach is not to aggregate all scenarios until a single scenario is left, but stop earlier. For example, we may take the pairwise average of scenarios until four of them are left. Solving the resulting problem with four scenarios will give a better result than with one scenario, but it is still hard. Fortunately, there are good approximation methods known for few scenarios, which makes it possible to beat the K-result for the first time.
This is the abstract:
As most robust combinatorial min-max and min-max regret problems with discrete uncertainty sets are NP-hard, research into approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path, or robust assignment problems.
In this paper we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an (εK)-approximation for any desired ε>0. Our method can be applied to min-max as well as min-max regret problems.
I just returned from a two-week visit to Hong Kong University of Science and Technology, which was made possible through the Kan Tong Po fellowship of the Royal Society. And I must say – I am most impressed, by both the wonderful city and the university.
As our work revolves around using public transport in emergency planning, I gave a talk on the very same topic as part of the department’s seminar series last Wednesday. It was a pleasure speaking to such an open and attentive audience.
We had a good start developing new ideas and models. Let’s see what will come out of it!
Last week I visited Imperial College and used the opportunity to discuss some of the classic and more recent results on robust selection problems in a talk of the same title.
When I first saw the selection problem, I thought it quite silly. Given a set of n items with a cost vector, choose p of those items that minimize the costs. An optimal solution is very simple to find: Just sort all items with respect to their costs, and pack the p cheapest ones. That’s all. So why is this interesting?
The trouble with most robust problems is that you add an additional layer of complexity through the handling of uncertainty. That means in many cases that you may start with a simple deterministic problem (say, shortest paths) and end up with an NP-hard robust counterpart. But the selection problem is so simple, that the complexity of the robust version (depending on concept and uncertainty set) tends to lie just between easy and hard. This makes it quite challenging to analyse.
As an example, as far as I know, the min-max regret counterpart of selection with interval uncertainty was the first problem of its kind that turned out to be solvable in polynomial time. With more such polynomial solvabilty results in what followed, it makes you wonder how far we can push the deterministic problem complexity and still stay in the realm of polynomial solution algorithms?
I am delighted the Royal Society decided to fund a travel exchange to the Hong Kong University of Science and Technology under the Kan Tong Po Fellowship Scheme (apparently named after the co-founder of the Bank of East Asia).
In our project titled “Optimisation Methods for Public Transport Utilisation in Evacuation Planning”, we will consider emergency situations where a densely populated, urban area needs to be evacuated. In this setting, an efficient public transportation system is required to move people quickly, as road networks become congested. Surprisingly, literature on this topic is relatively sparse, and most research focussed on the role of buses for emergency evacuations.
Much looking forward to our work in Hong Kong!
Last week, I was invited to give a talk on “Robust Combinatorial Optimisation: Complexity and Approximability” within the GRK1855 at the wonderfully-named TU Dortmund University. Many thanks for the hospitality!
We also used the opportunity to discuss the idea of min-max-min robust optimisation (also referred to as K-adaptivity). I’m much looking forward to see where our cooperation will lead us to!