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.
Hexaly, a new kind of hybrid optimization solver
Hexaly Optimizer is a new kind of hybrid optimization solver. Its modeling interface is nonlinear and set-oriented. In a sense, Hexaly APIs unify and extend modeling concepts from mixed-linear programming, nonlinear programming, and constraint programming. Under the hood, Hexaly combines various exact and heuristic optimization methods, such as branch-and-bound, automatic Dantzig-Wolfe reformulation, column and row generation, propagation methods, local search, direct search, and surrogate modeling techniques.
Regarding performance benchmarks, Hexaly distinguishes itself against the leading solvers in the market, like Gurobi, IBM Cplex, and Google OR Tools, by delivering fast and scalable solutions to Routing, Scheduling, Packing, Clustering, and Location problems.
This talk will introduce our set-based modeling formalism and show its scalability for large instances. We will then explore how the solver can use this formalism to automatically leverage state-of-the-art resolution techniques from both the exact and heuristic fields.
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.