EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2026. Computing the effect of multiple cost changes in combinatorial problems

Invited abstract in session WD-25: Topics in Combinatorial Optimization II (Contributed), stream Combinatorial Optimization.

Wednesday, 14:30-16:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Marcel Turkensteen
CORAL, Economics, Aarhus University
2. Gerold Jäger
Mathematics and Mathematical Statistics, Umeå University

Abstract

In this presentation, we consider sensitivity analysis to combinatorial optimization problems (or binary programming problems). In these problems, there is a ground set of elements, each of them with a given cost. The objective is to find a feasible combination of elements which, in our case, minimizes a total objective value.
Sensitivity analysis concerns finding the range of changes in cost values such that current solutions remain optimal. The supremum decrease and increase in a single element’s cost, the lower and upper tolerances, respectively, can be computed by solving an additional instance of the problem. When k element costs increase or decrease simultaneously, there is a k-dimensional area in which solutions remain optimal. Jäger et al. (2018, 2023) introduce set tolerances as the infimum and supremum sum of cost changes that lie inside and outside that area. For problems with sum objective, it requires solving an exponential number (in k) of instances to optimality to describe the area (Andersen et al, 2023) and to compute set tolerances.
We present new results which show that set tolerances of problems with a bottleneck objective (the objective value is the largest cost of the elements in a solution) require the solution of only one problem instance. We also show that tolerance computations can be independent of the choice of optimal solution.

Keywords

Status: accepted

Back to the list of papers