Concepts of Stability in Discrete Optimization Involving Generalized Addition Operations

Abstract

The paper addresses the tolerance approach to the sensitivity analysis of optimal solutions to the nonlinear optimization problem of the form $$\mbox{$\bigoplus\limits_{y\in S}C(y)\to\min$\quad over\quad $S\in\mathcal{S}$,}$$ where $\mathcal{S}$ is a collection of nonempty subsets of a finite set $X$ such that the union of $\mathcal{S}$ is $X$ and the intersection of $\mathcal{S}$ is empty, $C$ is a cost (or weight) function from $X$ into ${\mathbb{R}}^{+}=[0,\infty )$ or $(0,\infty )$, and $\oplus$ is a continuous, associative, commutative, nondecreasing and unbounded binary operation of generalized addition on ${\mathbb{R}}^{+}$, called an A-operation. We evaluate and present sharp estimates for upper and lower bounds of costs of elements from $X$, for which an optimal solution to the above problem remains stable. These bounds present new results in the sensitivity analysis as well as extend most known results in a unified way. We define an invariant of the optimization problem---the tolerance function, which is independent of optimal solutions, and establish its basic properties, among which we mention a characterization of the set of all optimal solutions, the uniqueness of optimal solutions and extremal values of the tolerance function on an optimal solution.

34 pages, 2 tables, LaTeX

Cited by in corpus (1)

• OneAdapt: Fast Configuration Adaptation for Video Analytics Applications via Backpropagation