CORAL Seminar: Marcel Turkensteen, Aarhus University

Title: Sensitivity analysis of combinatorial bottleneck problems

Info about event


Wednesday 22 April 2020,  at 14:15 - 15:30


Virtual Seminar by ZOOM

Presenter: Marcel Turkensteen, Aarhus University

Co-authors: Georld Jaeger, Umeå University, Sweden
Abstract: “In this presentation, we consider sensitivity analysis, the sensitivity of solutions to changes in parameter values. More specifically, we consider combinatorial optimization problems, in which feasible solutions consist of combinations of elements out of some given ground set, such as the Linear Assignment Problem and the Minimum Spanning Tree Problem. For these problems, upper and lower tolerances indicate the smallest increases and decreases in the costs of elements, respectively, such that current optimal solutions become non-optimal. Tolerance values help a decision maker to assess the sensitivity of optimal solutions to changes in cost values, but they have also been used in effective algorithms for NP-hard problems, such as Helsgaun’s version of the Lin-Kernighan heuristic for the Traveling Salesman Problem. For problems with objective of type sum (that is, the objective value of a solution is the sum of the costs of the selected elements), upper and lower tolerance computations are well established. However, for problems with objective of type bottleneck (that is, the objective value of a solution is the maximum of the costs of the selected elements), this is not so. In this presentation, we provide tolerance computations for these combinatorial bottleneck problems. The presentation focuses on the example of the Linear Bottleneck Assignment Problem, the bottleneck version of the Linear Assignment Problem. In this problem, n workers have to be assigned to n jobs, and the longest of all working times of all job-worker combinations should be minimized.”

Organsier: Sune Lauth Gadegaard