What’s new?

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!

Robust Selection Problems

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.