Conference program
Conference program
The conference program will be made available soon. The conference will start at 9.00 on the 22nd and finish around 13.30 on the 24th (the last session should finish around 12.15, followed by a lunch).
To avoid unnecessary paper waste, only electronic copies of the detailed overview as well as the booklet of the conference will be available.
Keynote speakers
The Traveling Salesman Problem: Package Deliveries, Pub Walks, and Astro Tours
Amazon drivers hit the road every day, each taking a delivery van in a traveling salesman problem (TSP) tour through 150 or more customer stops. Such instances can be readily solved to exact optimality, but the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations. We propose a simple and efficient penalty-based local search algorithm for route optimization in the presence of such constraints. The algorithm was used to win the $100,000 top prize in the Amazon Last Mile Routing Challenge, together with Stephan Held and Keld Helsgaun. We also describe recent progress on exact and approximate solutions to large-scale challenge instances of the TSP, including a shortest-possible walking tour to 81,998 bars in Korea and a 3D tour to 136,606,128 stars, guaranteed to be no more than 1.000144 times longer than a shortest-possible tour.
Explainable Optimization: New Perspectives and Challenges
In recent years, there has been a rising demand for transparent and explainable AI models. Although significant progress has been made in providing explanations for machine learning models, this topic has not received the same attention in the Operations Research (OR) community. However, algorithmic decisions in OR are made by complex algorithms which cannot be considered explainable or transparent as we will argue in this talk. We present two promising concepts to provide explanations for (integer) optimization problems. In the first part we introduce the concept of counterfactual explanations which asks the question: “How do the parameters of my problem have to be changed such that a different solution would be optimal”. In the second part we present fast model-agnostic methods which attempt to explain any type of optimization algorithm (exact or heuristic) by calculating contribution scores for each relevant problem parameter.
Semidefinite programming based bounds for the quadratic minimum spanning tree problem
In the quadratic minimum spanning tree problem (QMSTP), the goal is to minimize a quadratic objective over the set of all spanning trees of a graph. In this talk, we show how the QMSTP can be formulated as mixed-integer semidefinite program by exploiting the algebraic connectivity of the underlying graph. Based on these formulations, we derive a doubly nonnegative (DNN) relaxation of the QMSTP and introduce valid inequalities that strengthen this relaxation using the Chvátal–Gomory procedure for mixed-integer conic programming. We also present a variant of the Peaceman–Rachford splitting method that enables us to solve the DNN relaxation efficiently and obtain strong bounds for the QMSTP.
Joint work with Frank de Meijer, Melanie Siebenhofer and Renata Sotirov.