Prof. William Cook, University of Waterloo
Title: The Traveling Salesman Problem: Amazon Deliveries, Pub Walks, and Astro Tours
Abstract: The traveling salesman problem, or TSP for short, has long served as a chal
lenge in discrete optimization. The work dates back to Dantzig, Fulkerson, and Johnson's amazing solution of a 49-city problem with by-hand calculations in 1954. Dantzig's team produced both a tour and a linear-programming proof that it is shortest possible. For current TSP challenges, we discuss methods used to find a shortest walking tour to 81,998 bars in South Korea. And, together with David Applegate and Keld Helsgaun, a tour through the 3D positions of 136,606,128 stars that is guaranteed to be no more than 1.00015 times longer than a shortest-possible tour. Going practical, we also discuss methods used to compute constrained tours for delivery-van drivers. This van-routing work, together with Stephan Held and Keld Helsgaun, won the $100,000 top prize in the Amazon Last Mile Routing Challenge held in 2021. Throughout the talk, we will present open research questions that could drive further improvements in cutting-plane methods for the TSP and related discrete optimization models.
Prof. Gábor Galambos, University of Szeged
Title: On the Coupled of Task Problems
Abstract: In the coupled task problem (CTP) we have to schedule n jobs on a single machi
ne, each consisting of two tasks with exact time delays in between, while an objective function has to be minimized. The problem of scheduling coupled tasks with exact delays was first published by Shapiro in his pioneering paper in 1980. He considered the problem in which one had to find the minimum of the makespan of the last scheduled job. After that, research focused for a long time only on problems where the goal was to minimize makespan
( 1 | (aj , Lj , bj) | max Cj ). In the first part of the talk, we will show the results that came while examining the complexity of problems with different parameters, and we will also review results came up for approximation algorithms. When examining new problems, Bo Chen and his co-author opened a new chapter when they began to examine problems in which the objective function was to minimize the sum of the completion costs of the jobs ( 1 | (aj , Lj , bj) | Σ Cj ). This accelerated the investigation of problems with such objective functions, leading to several complexity results and worst-case analysis of approximation algorithms. We will review these results and point out directions that seem promising for future research. We conclude the talk with examination of a problem in which the objective func tion is the sum of the earliness and tardiness costs associated with scheduled jobs ( 1 | (aj , Lj , bj) | Σ ( Ej + Tj ) ).
Prof. Joerg Kalcsics, University of Edinburgh
Title: Firefighter Games on Graphs
Abstract: In firefighter games, a fire breaks out in a fixed set of vertices of a connected undirect
ed graph at time step 0. In each subsequent time step, first a certain number of vertices can be defended before the fire spreads to all non-burning undefended neighbours of the burning vertices. Once a vertex is either burning or defended, it remains so for the rest of the game. The game ends when the fire cannot spread further. The goal of the defenders is to find a strategy that maximizes the number of non-burning vertices. The problem was first introduced by Hartnell in 1995 and the decision version of the game with one defender and starting fire was shown to be NP-complete even on trees with a maximum degree of three if the fire breaks out on a vertex of degree three. Firefighter games are an abstraction of various disease intervention strategies, including administering a vaccine that prevents the vertex from being infected or from spreading the disease to other vertices; or an intervention that simply removes individuals from the area and thus from the path of the disease. Such interventions have been used, for example, to save endangered species from the chrytridiomycosis pandemic. The vertices hereby model individuals, with edges connecting individuals between whom disease could spread (for instance, if they regularly come within a certain physical distance for airborne transmission). Alternatively, the vertices could model population centres, with edges joining centres that in real life are linked by transportation and regularly have individuals traveling between them, potentially spreading the disease. Other applications include, e.g., stopping a computer virus from spreading on a network or hampering the spread of fake news on social media networks. Furthermore, firefighter games play a significant role in addressing open questions in fire management techniques, e.g., to optimize resource allocation in firefighting strategies. As the problem is NP-hard even on trees, a lot of research has focussed on specialized networks, most notably grids, on asymptotic results, and on approximation algorithms. We will formally introduce the game and review some of those results. Moreover, we look at several extensions of the classic game. For example, edge-defence firefighter games where edges instead of vertices are defended, cost-value firefighter games where there is a cost and a benefit associated with defending a vertex, distance-limited firefighter games where defenders can only move a certain distance between time steps, and stochastic firefighter games where spread along edges is probabilistic and not deterministic.
Prof. Sergio García Quiles, University of Edinburgh
Title: Facility location models with preferences constraints
Abstract: In facility location problems, we have to open some facilities from a set of potential locations and allocat
e customers to the open facilities so that a certain objective function is optimized (for example, minimum allocation cost or distance travelled). Although many problems assume that the location and allocation parts are done at the same time or follow the same criteria, sometimes the locator has no control over which facility customers will attend once the location decisions have been made. Therefore, it is important to include the customers preferences. When we include these preferences in the form of constraints, we have a problem that is harder to solve, and even further complications appear if we have capacities. This presentation will will give an overview of models for facility location problems with preferences for both the uncapacitated and capacitated case, including the use of valid inequalities to strenghten the formulations and solution methods illustrated with a computational study.