Assessing the effect of multiple cost changes using reverse set tolerances

TY - JOUR

T1 - Assessing the effect of multiple cost changes using reverse set tolerances

AU - Jaeger, Gerold

AU - Turkensteen, Marcel

PY - 2024/9

Y1 - 2024/9

N2 - We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance, which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal. We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications.

AB - We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance, which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal. We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications.

KW - Combinatorial optimization

KW - Reverse set tolerance

KW - Sensitivity analysis

KW - Tolerance

UR - http://www.scopus.com/inward/record.url?scp=85142695036&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.10.018

DO - 10.1016/j.dam.2022.10.018

M3 - Journal article

SN - 0166-218X

VL - 354

SP - 279

EP - 300

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -