I am in Bonn, Germany for the EURO Conference. Tons of people here (2200+) but the organizers seem to be coping very well. Last night was a nice reception in a beer garden nearby. It has been a long time since I was at a conference with unlimited free beers. This morning was a little … slow.
The opening plenary session today included the announcement and talks of this year’s EURO Gold Medal winners: Jacques Benders, Eindhoven, and Frank Kelly, University of Cambridge. I missed most of the session (thanks, Graham Rand, for letting me know the winners), and I am really kicking myself for missing Benders’ talk: his work has a huge influence on my own current research. Benders’ Decomposition is one of the fundamental tools of operations research. Recently, people like John Hooker have breathed new life into the approach by introducing logical Benders’ decomposition (or combinatorial Benders decomposition).
Benders’ decomposition works as follows: take an optimization problem with two types of variables, x and y. First, solve the problem using only constraints that include just the x variables (this is the master problem). Give a solution x* to the master problem, now solve for the optimal y (the subproblem). We now have a candidate solution (x*,y*). The key step is to now generate a constraint on the x variables that says: “If you want a better x, it has to satisfy this constraint”. In classical Benders decomposition, that constraint is formed from the dual solution to the subproblem. In logical Benders, techniques such as constraint programming can be used to identify appropriate constraints. This iterates until the master problem (with the additional constraints) shows there is no better x than the ones already generated.
This approach can be radically faster than solving the overall (x,y) problem as one monolithic optimization. As the introduction to a reprinting of Benders’ original work says:
The real importance of the introduced algorithm is more evident today than ever before. It has had a profound seminal influence on the development of new generation of algorithms that enable us to solve ever larger and more complex from a wide spectrum.
I did get to the last half of Kelly’s talk. This was a very nice talk on modeling network routing, including issues of fairness. This happens a lot in internet routing of course, where routers try to figure out where things should go, and try to let everything through (eventually at least!). It would be rather annoying if one line through a router had a permanent “stop sign” while other traffic was sent through. Frank is famous enough to have a Wikipedia page.
Congrats to both Jacques and Frank, and no more missing plenary sessions for me!