Sensitivity Analysis of the Cost Coefficients in Multiobjective Integer Linear Optimization

This paper considers sensitivity analysis of the cost coefficients in multiobjective integer linear programming problems. We define the sensitivity region as the set of simultaneous changes to the 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, and we show that this is sufficient for the efficient set to be the same upon changes. For a single coefficient, we show that 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. Finally, we show that the sensitivity region is a convex set (an interval). Our approach generalizes to simultaneous changes in multiple coefficients. For illustration, we consider mean-variance capital budgeting and determine the region for which the set of efficient portfolios remains the same, despite a misspecification or a change in the net present values of the projects. Further computational experience with multiobjective binary and integer knapsack problems demonstrates the general applicability of our technique. For instance, we obtain all sensitivity intervals for changes to single coefficients of biobjective problems with 500 binary variables in less than half an hour of CPU time by excluding a large number of inefficient solutions. In fact, the number of excluded solutions is above 100 orders of magnitude larger than the number of remaining solutions.