This week the International Symposium on Mathematical Programming (ISMP) has been taking place in Berlin. It's the world congress of mathematical optimisation, which drew over 2,000 scientists and members of industry to Germany's capital. But what exactly were they talking about? Andreas Loos and Thomas Vogt of the German Mathematical Society spoke for Plus to Martin Skutella, of the Technical University of Berlin, an expert in the field and chair of ISMP's organising committee.
Martin Skutella.
Loos & Vogt: "Mathematical programming" sounds a bit like all the participants are sitting behind computers writing software?
Skutella: The notion comes from history. I think it was [the mathematician] John von Neumann who proposed at the end of the 1940s to call that field of mathematics mathematical programming because it sounded cool, modern and ensured state funding. In fact, however, mathematical programming consists in developing models, algorithms, and tools to solve optimisation problems. So: if you hear math programming, simply think of optimisation.
Loos & Vogt: What kind of problems do you optimisers tackle?
Skutella: Oh, the bandwidth is incredibly large – it goes from problems like finding shortest routes avoiding traffic jams in navigation hand-helds, and industrial applications in logistics, production planning or telecommunication, to problems from economics: which stocks do you buy or sell, how do you optimise your portfolio? A growing part of applications comes from energy providers. Think for instance of a pool of [solar] panels; the owners want to sell the electric energy to the energy market. But they have to guarantee that they can deliver any time. So, when the Sun is behind clouds, they have to buy electricity (or use stored electricity). And if the Sun is shining, they have probably more energy than needed – and have to take care not to overload their network. This leads to complicated optimisation problems.
This is a two-dimensional polytope. Image: Ylloh.
Loos & Vogt: What are the main theoretical questions in the area?
Skutella: There is still a lot to do on traditional fields like the travelling salesman problem or other classic combinatorial problems. [The travelling salesman problem involves finding the shortest route visiting all of a given number of cities. It's incredibly hard to solve, see here for more.] But there are also new questions emerging. An important one concerns the combinatorial diameter of polytopes. [These are geometric objects with flat sides, for example polygons in two dimensions and polyhedra in three dimensions.]
Loos & Vogt: What's the combinatorial diameter of a polytope?
Here's a cube. To move between any two corners (vertices) you have to move down at most three edges. So the cube's combinatorial diameter is 3.
Skutella: Imagine a cube in three dimensions – then two vertices can either have "distance" one (which means you can reach the next vertex simply by wandering along one edge) or two (you can reach it by sliding along two edges with a vertex between them) or they are three edges apart. Therefore, one says that the cube has diameter three. There was a conjecture from the 1970s that said that there is a certain maximum diameter for a general polytope, depending on its dimension and the number of faces. In 2010, Francisco Santos found a counterexample: a polytope in 43 dimensions with 86 faces and a diameter that is bigger than the conjecture said. This triggered a lot of research in that field. Santos also spoke at the ISMP.
Loos & Vogt: What were the highlights of this year's ISMP?
Skutella: With more than 2,000 participants we had more attendants than any ISMP before. We had five plenary talks of outstanding mathematicians; and there have been six prizes awarded – one of which is new, the Paul Y. Tseng memorial Lectureship. This prize was established in 2011; it was presented for the first time at the ISMP. The lectureship was established to remember Paul Y. Tseng, who died in 2009 on a kayak tour on the Yangtze river shortly before the ISMP of that year. Another important thing is that we had a grant for participants from 3rd world countries.
Loos & Vogt: What does the future of mathematical programming look like?
Skutella: Sub-areas overlap more and more. Different sub-communities come closer each day and don't work separately like they did, let's say, ten years ago. Another development is that there's more and more computational optimisation. Computer software has become more and more powerful during recent years. We have more and more powerful solvers, and this trend will certainly continue.
On the other hand, problems become more and more complex. Imagine the optimisation of [a public transport system for a city of the size] of Berlin. We have optimised the traffic of the underground trains of Berlin with good results – but we are far away of optimising the whole Berlin transport system including metro, buses, express trains and [trams]. We would like to do so, but we don't have the means yet. There is still a lot to do!
About the authors
Andreas Loos is a mathematician at Freie Universität Berlin and a freelance science writer. Thomas Vogt is leading the Media Office of the German Mathematical Association.