EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1529. Sensitivity analysis of the cost coefficients in multi-objective integer linear optimization

Invited abstract in session MC-52: Multi-objective Combinatorial Optimization, stream Combinatorial Optimization.

Monday, 12:30-14:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Britta Efkes
Department of Mathematics and Informatics, University of Wuppertal
2. Kim Allan Andersen
CORAL, Department of Business Studies, Aarhus School of Business
3. Trine Krogh Boomsma
Department of Mathematical Sciences, University of Copenhagen
4. Nicolas Forget
Institute of Production and Logistics Management, Johannes Kepler University Linz

Abstract

We consider sensitivity analysis of the cost coefficients in multi-objective integer linear programming problems and define the sensitivity region as the set of simultaneous changes to the objective function coefficients for which the efficient set and its structure remain the same. In particular, we require that the component-wise relation between efficient solutions is preserved and that inefficient solutions remain inefficient.
We present necessary and sufficient conditions on permissible changes that satisfy the defined properties. In this talk we concentrate on changes to a single objective function coefficient and show that the sensitivity region is a convex set, i.e., an interval.
In order to avoid going through all pairs of feasible and efficient solutions, we introduce further properties that identify inefficient solutions that remain inefficient whatever the change is. Based on this, a subset of the inefficient solutions can be excluded from consideration. More specifically, we prove that it suffices to inspect the inefficient solutions of a q-objective problem that are efficient in one of two related (q + 1)-objective problems, in the case of only one change.
Computational experiments with multi-objective binary and integer knapsack problems demonstrate the general applicability of our technique.

Keywords

Status: accepted

Back to the list of papers