# Extending the definition of set tolerances

Gerold Jäger  Department of Mathematics and Mathematical Statistics,
University of Umeå,
SE-90187 Umeå, Sweden,
<EMAIL_ADDRESS>Marcel Turkensteen  Department of Economics and Business,
School of Business and Social Sciences,
University of Aarhus,
Fuglesangs Alle 4,
DK-8210 Aarhus, Denmark,
<EMAIL_ADDRESS>
###### Abstract

Optimal solutions of combinatorial optimization problems can be sensitive to
changes in the cost of one or more elements. Single and set tolerances measure
the largest / smallest possible change such that the current solution remains
optimal and other solutions become non-optimal for cost changes in one or more
elements, respectively. The current definition only applies to subsets of
elements. In this paper, we broaden the definition to all elements, for single
tolerances, and to all subsets of elements for set tolerances, while proving
that key computational and theoretical properties still apply to the new
definitions.

###### keywords:

Sensitivity analysis, single tolerance, set tolerance

##  1 Introduction

The theory of tolerances is a branch of sensitivity analysis for combinatorial
optimization problems. It determines limits to the changes in the costs of
elements or sets of elements such current solutions remain optimal or other
solutions become optimal.

In fact, tolerances are frequently used to estimate the effect of parameter
changes on the optimality of solutions GJM06b ; JT18 ; JT23 . Furthermore, the
usage of tolerances has led to effective heuristics and exact approaches for
many famous problems, most importantly the Traveling Salesman Problem GGT12 ;
Hel00 ; JDGMR14 ; TGGS08 . Previous studies defined three types of tolerances
and determined their relevant theoretical properties, namely single tolerances
GJM06b , regular set tolerances JT18  and reverse set tolerances JT23 , where
the first can be viewed as a special case of the latter two. A single element
/ set of elements of the ground set can have two tolerance values, an upper
tolerance and a lower tolerance. The drawback of the current definition of
single and set tolerances is that it covers only specific subsets of elements
in the ground set. For example, if an element does not belong to an optimal
solution or a set of elements is not part of a given optimal solution, no
upper tolerance value is defined.

In this work we generalize the definition and extend the theory of set
tolerances in such a way that these drawbacks no longer hold. We show that all
extended definitions are consistent with the corresponding original ones. We
further prove that several previous results, in particular exact values and
upper and lower bounds, can be generalized for the new definitions so that the
main part of the previous theory can be kept.

##  2 Notations, definitions, and existing results

For the sake of completeness and readability of this work, we present
notations and the definitions of single upper/lower tolerances, defined in
GJM06b . regular set upper/lower tolerances, defined in JT18 , and of reverse
set upper/lower tolerances, defined in JT23 . For all types of tolerances we
present exact computations, or in case they are not known, upper and lower
bounds.

###  2.1 Combinatorial minimization problems

Formally, a _c_ ombinatorial minimization problem (CMP) ${\cal P}$ is given by
a tuple $({\cal E},D,c,f_{c})$ where ${\cal E}$ is a finite _ground set of
elements_ , $D\subseteq 2^{\cal E}\setminus\\{\emptyset\\}$ is the set of
_feasible solutions_ , $c:\,{\cal E}\to\mathbb{R}$ is the _cost function_
which assigns costs to each single element of ${\cal E}$,
$f_{c}:\,D\to\mathbb{R}$ is a function which depends on the function $c$ and
assigns costs to each feasible solution $D$.

$S^{\ast}\subseteq{\cal E}$ is called an _optimal solution_ of ${\cal P}$ if
$S^{\ast}$ is a feasible solution and the costs $f_{c}(S^{\ast})$ of
$S^{\ast}$ are minimum. We denote the costs of an optimal solution $S^{\ast}$
of ${\cal P}$ by $f_{c}({\cal P})$ and the set of optimal solutions by
$D^{\ast}$.

We only consider CMPs ${\cal P}=({\cal E},D,c,f_{c})$ where
$f_{c}:\,D\to\mathbb{R}$ is of type _sum_ , i.e., the sum of all costs is
minimized and which we call a _combinatorial sum problem (CSP)_ , of type
_product_ , i.e., the product of all costs is minimized (additionally, in this
case all costs must be positive), and which we call a _combinatorial product
problem (CPP)_ or of type _bottleneck_ , i.e., the maximum of all costs is
minimized, and which we call a _combinatorial bottleneck problem (CBP)_.
Moreover, there is at least one optimal solution of ${\cal P}$, i. e.,
$D^{\ast}\not=\emptyset$. Define

$\delta(e):=\left\\{\begin{array}[]{ll}\infty,&\mbox{if $f_{c}$ is of type sum
or bottleneck}\\\ c(e),&\mbox{if $f_{c}$ is of type
product}\end{array}\right.$

as the supremum by which element $e$ can be decreased such that $f_{c}$
remains either of type sum, product, or bottleneck. For a CBP, let $c^{\ast}$
denote the objective value of an optimal solution, so $c^{\ast}=f_{c}({\cal
P})$.

Let a CMP ${\cal P}=({\cal E},D,c,f_{c})$ and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\subseteq{\cal E}$ be given. We obtain a new
combinatorial minimization problem if for all $l\in\mathbb{N}$ with $1\leq
l\leq k$ we add $\alpha_{l}\in\mathbb{R}$ to the cost of $e_{l}$. We denote
the new problem by ${\cal P}_{c_{{\vec{\alpha}},{E}}}=({\cal
E},D,c_{\vec{\alpha},E},{f_{c_{\vec{\alpha},E}}})$, which is formally defined
as
$c_{\vec{\alpha},e}(\bar{e})=\left\\{\begin{array}[]{cl}c(\bar{e}),&\mbox{if}\
\bar{e}\in{\cal E}\setminus E\\\ c(\bar{e})+\alpha_{l},&\mbox{if}\
\bar{e}=e_{l}\end{array}\right.$ for all $\bar{e}\in{\cal E}$. Note that
${f_{c_{\vec{\alpha},E}}}$ is of the same type as $f_{c}$, unless $f_{c}$ is
of type product and $\alpha_{l}\leq-c(e_{l})$ for at least one
$l\in\\{1,2,\dots,k\\}$. When $|E|=1$ with $E=\\{e\\}$, we write ${\cal
P}_{c_{{\alpha},{e}}}=({\cal E},D,c_{\alpha,e},{f_{c_{\alpha,e}}})$, for the
sake of simplicity, instead of the formally correct notation with $\\{e\\}$.

For $M\subseteq D$, we denote the costs of the best solution included in $M$
by $f_{c}(M)$. The costs $f_{c}(M)$ for $M=\emptyset$ are defined as infinite,
i. e., $\infty$.

Let $e\in{\cal E}$. We denote the set of feasible solutions of $D$ such that
each of them does not contain $e\in{\cal E}$ by $D_{-}(e)$, i. e.,
$D_{-}(e)=\\{\,S\in D\mid e\in{\cal E}\setminus S\\}$. Analogously, we denote
the set of feasible solutions of $D$ such that each of them contains
$e\in{\cal E}$ by $D_{+}(e)$, i. e., $D_{+}(e)=\\{\,S\in D\mid e\in S\\}$.

###  2.2 Single upper tolerances

Let ${\cal P}$ be an instance, $S^{\ast}$ an optimal solution of ${\cal P}$,
and $e\in S^{\ast}$. Then the _upper tolerance_ $u_{S^{\ast}}({e})$ is defined
as follows GJM06b :

$\displaystyle u_{S^{\ast}}({e})$ $\displaystyle:=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}_{0}^{+}\mid S^{\ast}\ \mbox{is
optimal for}\ {\cal P}_{c_{{\alpha},{e}}}\\}.$

By (GJM06b, , Theorem 2), it holds for an instance ${\cal P}$ that the upper
tolerance does not depend on a particular optimal solution of ${\cal P}$.
Therefore, we refer to the upper tolerance of $e$ with respect to an optimal
solution $S^{\ast}$ as the upper tolerance of $e$ with respect to ${\cal P}$,
$u_{{\cal P}}({e})$. Let

$\displaystyle UTE_{{\cal P}}$ $\displaystyle:=$ $\displaystyle\\{e\in{\cal
E}\mid\exists\,S^{\ast}\in D^{\ast}:\,e\in S^{\ast}\\}$

be the set of elements in ${\cal E}$ for which the upper tolerance is defined
with respect to ${\cal P}$. Obviously, it holds that:

$\displaystyle UTE_{{\cal P}}$ $\displaystyle=$
$\displaystyle\bigcup_{S^{\ast}\in D^{\ast}}S^{\ast}.$

######  Theorem 1.

(GJM06b, , Theorem 4) Let ${\cal P}$ be an instance and $e\in UTE_{{\cal P}}$.
Then the following holds:

(a)

$u_{{\cal P}}({e})=f_{c}(D_{-}(e))-f_{c}({\cal P})$, if $f_{c}$ is of type
sum.

(b)

$u_{{\cal P}}({e})=\frac{f_{c}(D_{-}(e))-f_{c}({\cal P})}{f_{c}({\cal
P})}\cdot c(e)$. if $f_{c}$ is of type product.

(c)

$u_{{\cal P}}({e})=f_{c}(D_{-}(e))-c(e)$, if $f_{c}$ is of type bottleneck.

###  2.3 Single lower tolerances

Let ${\cal P}$ be an instance, $S^{\ast}$ an optimal solution of ${\cal P}$,
and $e\in{\cal E}\setminus S^{\ast}$. The _lower tolerance_ of $e$ with
respect to $S^{\ast}$ is defined as follows GJM06b :

$\displaystyle l_{S^{\ast}}({e})$ $\displaystyle:=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}_{0}^{+}\mid S^{\ast}\ \mbox{is
optimal for}\ {\cal P}_{c_{{-\alpha},{e}}}\\}.$ (1)

By (GJM06b, , Theorem 8), it holds for an instance ${\cal P}$ that the lower
tolerance does not depend on a particular optimal solution. Therefore, we
define the lower tolerance of $e$ with respect to ${\cal P}$, $l_{{\cal
P}}({e})$. Let

$\displaystyle LTE_{{\cal P}}$ $\displaystyle:=$ $\displaystyle\\{e\in{\cal
E}\mid\exists\,S^{\ast}\in D^{\ast}:\,e\in{\cal E}\setminus S^{\ast}\\}$

be the set of elements in ${\cal E}$ for which the lower tolerance is defined
with respect to ${\cal P}$. Obviously, it holds that:

$\displaystyle LTE_{{\cal P}}$ $\displaystyle=$ $\displaystyle{\cal
E}\setminus\bigcap_{S^{\ast}\in D^{\ast}}S^{\ast}.$

Algorithm 1 of TJ22  computes the sets $UTE_{{\cal P}}$ and $LTE_{{\cal P}}$
for CBPs. It uses so-called smallest includes and the set $MUL_{{\cal
P}}=UTE_{{\cal P}}\cap LTE_{{\cal P}}$, leading to a computationally
challenging algorithm. This motivates the purpose of this work to extend the
definition of tolerances to _all_ single elements / subsets.

Let $OPT_{{\cal P}}$ be the set containing the elements that belong to all
optimal solutions, i. e., $OPT_{{\cal P}}\;=\;\bigcap_{S^{\ast}\in
D^{\ast}}S^{\ast}\;={\cal E}\setminus LTE_{{\cal P}}$.

######  Theorem 2.

(GJM06b, , Theorem 11) For ${\cal P}$ be an instance and $e\in LTE_{{\cal
P}}$. Then the following holds:

(a)

$l_{{\cal P}}({e})=f_{c}(D_{+}(e))-f_{c}({\cal P})$, if $f_{c}$ is of type
sum,

(b)

$l_{{\cal P}}({e})=\frac{f_{c}(D_{+}(e))-f_{c}({\cal
P})}{f_{c}(D_{+}(e))}\cdot c(e)$, if $f_{c}$ is of type product,

(c)

$l_{{\cal P}}({e})=\left\\{\begin{array}[]{cl}c(e)-c^{\ast},&\mbox{if
$g(e)<c^{\ast}$}\\\ \infty,&\mbox{otherwise}\end{array}\right.$, where
$c^{\ast}:=f_{c}({\cal P})$ and

$\displaystyle g(e):=\left\\{\begin{array}[]{cc}\min_{S\in D_{+}(e)}\max_{a\in
S\setminus\\{e\\}}\\{c(a)\\},&\mbox{if $D_{+}(e)\not=\emptyset$}\\\
\infty,&\mbox{if $D_{+}(e)=\emptyset$}\end{array}\right.,$

if $f_{c}$ is of type bottleneck.

###  2.4 Regular and Reverse Set Upper Tolerances

Let ${\cal P}$ be an instance, $S^{\ast}$ an optimal solution for ${\cal P}$,
and $E=\\{e_{1},e_{2},\dots,e_{k}\\}\subseteq S^{\ast}$. Define the regular
set upper tolerance of $E$ as follows JT18 :

$\displaystyle u_{S^{\ast}}({E}):=\\!\\!$
$\displaystyle\sup\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\alpha=\sum_{l=1}^{k}\alpha_{l},\;\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq 0,\;S^{\ast}\
\mbox{is optimal for}\ {\cal P}_{c_{{\vec{\alpha}},{E}}}\Big{\\}}.$

Define the reverse set upper tolerance of $E$ as follows JT23 :

$\displaystyle\bar{u}_{S^{\ast}}({E}):=\\!\\!$
$\displaystyle\inf\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\alpha=\sum_{l=1}^{k}\alpha_{l},\;\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq 0,\;S^{\ast}\
\mbox{is not optimal for}\ {\cal P}_{c_{{\vec{\alpha}},{E}}}\Big{\\}}.$

By (JT18, , Theorem 7) it holds for an instance ${\cal P}$ that the regular
set upper tolerance does not depend on a particular optimal solution of ${\cal
P}$. Therefore, we refer to the regular set upper tolerance of $E$ with
respect to an optimal solution $S^{\ast}$ as the regular set upper tolerance
of $E$ with respect to ${\cal P}$.

Analogously, by (JT23, , Theorem 1) it holds for an instance ${\cal P}$ that
the reverse set upper tolerance does not depend on a particular optimal
solution of ${\cal P}$. Therefore, we refer to the reverse set upper tolerance
of $E$ with respect to an optimal solution $S^{\ast}$ as the reverse set upper
tolerance of $E$ with respect to ${\cal P}$.

Let

$\displaystyle UTS_{{\cal P}}$ $\displaystyle:=$
$\displaystyle\\{E\subseteq{\cal E}\mid\exists\,S^{\ast}\in
D^{\ast}:\,E\subseteq S^{\ast}\\}$

be the set of subsets of ${\cal E}$ for which the regular/reverse set upper
tolerance is defined with respect to ${\cal P}$. By definition, it holds that:

$\displaystyle\bar{u}_{{\cal P}}({E})\;\leq\;u_{{\cal P}}({E}),$
$\displaystyle u_{{\cal P}}({\\{e\\}})\;=\;\bar{u}_{{\cal
P}}({\\{e\\}})\;=\;u_{{\cal P}}({e}).$

######  Theorem 3.

(JT18, , Theorem 9) Let ${\cal P}$ be an instance and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\in UTS_{{\cal P}}$. Then the following holds:

(a)

$\max_{l=1}^{k}\,\\{u_{{\cal P}}({e_{l}})\\}\;\leq\;u_{{\cal P}}({E})$.

(b)

If $f_{c}$ is of type sum or product, $u_{{\cal
P}}({E})\;\leq\;\sum_{l=1}^{k}u_{{\cal P}}({e_{l}})$.

(c)

If $f_{c}$ is of type bottleneck, $\sum_{l=1}^{k}u_{{\cal
P}}({e_{l}})\;\leq\;u_{{\cal P}}({E})$.

######  Theorem 4.

(JT23, , Theorem 3, 4) Let ${\cal P}$ be an instance and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\in UTS_{{\cal P}}$. Then the following holds:

(a)

$\bar{u}_{{\cal P}}({E})\leq\min_{l=1}^{k}\,\\{u_{{\cal P}}({e_{l}})\\}$.

(b)

If $f_{c}$ is of type sum or bottleneck, $\bar{u}_{{\cal
P}}({E})\;=\;\min_{l=1}^{k}\\{u_{{\cal P}}({e_{l}})\\}$.

(c)

If $f_{c}$ is of type product,
$\left(\sqrt[k]{\min_{l=1}^{k}\left\\{\frac{u_{{\cal
P}}({e_{l}})}{c(e_{l})}\right\\}+1}-1\right)\cdot\min_{l=1}^{k}\,\\{c(e_{l})\\}\;\leq\;\bar{u}_{{\cal
P}}({E})$.

###  2.5 Regular and Reverse Set Lower Tolerances

Let ${\cal P}$ be an instance, $S^{\ast}$ an optimal solution of ${\cal P}$,
and $E=\\{e_{1},e_{2},\dots,e_{k}\\}\subseteq{\cal E}\setminus S^{\ast}$.
Define the regular set lower tolerance of $E$ as follows JT18 :

$\displaystyle l_{S^{\ast}}({E})\\!\\!$ $\displaystyle:=$
$\displaystyle\sup\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\alpha=\sum_{l=1}^{k}\alpha_{l},\;\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle
0\leq\alpha_{1}<\delta(e_{1}),\,0\leq\alpha_{2}<\delta(e_{2}),\dots,$
$\displaystyle 0\leq\alpha_{k}<\delta(e_{k}),\;S^{\ast}\ \mbox{is optimal
for}\ {\cal P}_{c_{{-\vec{\alpha}},{E}}}\Big{\\}}.$

Define the reverse set lower tolerance $l_{S^{\ast}}({E})$ of $E$ as follows
JT23 :

$\displaystyle\bar{l}_{S^{\ast}}({E})\\!\\!$ $\displaystyle:=$
$\displaystyle\inf\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\alpha=\sum_{l=1}^{k}\alpha_{l},\;\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle
0\leq\alpha_{1}<\delta(e_{1}),\,0\leq\alpha_{2}<\delta(e_{2}),\dots,$
$\displaystyle 0\leq\alpha_{k}<\delta(e_{k}),\;S^{\ast}\ \mbox{is not optimal
for}\ {\cal P}_{c_{{-\vec{\alpha}},{E}}}\Big{\\}}.$

By (JT18, , Theorem 13) it holds for an instance ${\cal P}$ that the regular
set lower tolerance does not depend on a particular optimal solution of ${\cal
P}$. Therefore, we refer to the regular set lower tolerance of $E$ with
respect to an optimal solution $S^{\ast}$ as the regular set lower tolerance
of $E$ with respect to ${\cal P}$.

Analogously, by (JT23, , Theorem 7) it holds for an instance ${\cal P}$ that
the reverse set lower tolerance does not depend on a particular optimal
solution of ${\cal P}$. Therefore, we refer to the reverse set lower tolerance
of $E$ with respect to an optimal solution $S^{\ast}$ as the reverse set lower
tolerance of $E$ with respect to ${\cal P}$.

Let

$\displaystyle LTS_{{\cal P}}:=\\{E\subseteq{\cal
E}\;\Big{|}\;\exists\,S^{\ast}\in D^{\ast}:\,E\subseteq{\cal E}\setminus
S^{\ast}\\}$

be the set of subsets of ${\cal E}$ for which the regular/reverse set lower
tolerance is defined with respect to ${\cal P}$. By definition, it holds that:

$\displaystyle\bar{l}_{{\cal P}}({E})\;\leq\;l_{{\cal P}}({E}),$
$\displaystyle l_{{\cal P}}({\\{e\\}})\;=\;\bar{l}_{{\cal
P}}({\\{e\\}})\;=\;l_{{\cal P}}({e}).$

######  Theorem 5.

(JT18, , Theorem 17) Let ${\cal P}$ be an instance and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\in LTS_{{\cal P}}$. Then the following holds:

(a)

$\max_{l=1}^{k}\,\\{l_{{\cal P}}({e_{l}})\\}\;\leq\;l_{{\cal
P}}({E})\;\leq\;\sum_{l=1}^{k}l_{{\cal P}}({e_{l}})$.

(b)

If $f_{c}$ is of type bottleneck, $l_{{\cal
P}}({E})\;=\;\sum_{l=1}^{k}l_{{\cal P}}({e_{l}})$.

######  Theorem 6.

(JT23, , Theorem 9) Let ${\cal P}$ be an instance and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\in LTS_{{\cal P}}$. Then the following holds:

(a)

$\bar{l}_{{\cal P}}({E})\;\leq\;\min_{l=1}^{k}\,\\{l_{{\cal P}}({e_{l}})\\}$.

(b)

If $f_{c}$ is of type sum or product, $\bar{l}_{{\cal
P}}({E})\;=\;\min_{l=1}^{k}\\{l_{{\cal P}}({e_{l}})\\}$.

##  3 Examples

######  Example 1.

$\bullet$

${\cal E}=\\{w,x,y,z\\}$ with $c(w)=3$, $c(x)=5$, $c(y)=4$, $c(z)=6$,

$\bullet$

$D=\\{\,\\{w,x\\},\,\\{y,z\\}\\}$,

$\bullet$

$f_{c}$ is of type sum.

It holds that:

$\bullet$

$S_{1}:=\\{w,x\\}$ is optimal with cost $8$, whereas $S_{3}:=\\{y,z\\}$ is
non-optimal with cost $10$.

######  Example 2.

$\bullet$

${\cal E}=\\{v,w,x,y,z\\}$ with $c(v)=2$, $c(w)=3$, $c(x)=5$, $c(y)=4$,
$c(z)=8$,

$\bullet$

$D=\\{\,\\{v,x\\},\,\\{w,y\\},\,\\{z\\}\\}$,

$\bullet$

$f_{c}$ is of type sum.

It holds that:

$\bullet$

$S_{1}:=\\{v,x\\}$ and $S_{2}:=\\{w,y\\}$ are optimal with cost $7$, whereas
$S_{3}:=\\{z\\}$ is non-optimal with cost $8$.

######  Example 3.

$\bullet$

${\cal E}=\\{v,w,x,y,z\\}$ with $c(v)=2$, $c(w)=3$, $c(x)=6$, $c(y)=4$,
$c(z)=24$,

$\bullet$

$E=\\{v,w\\}$, $e_{1}=v$, $e_{2}=w$,

$\bullet$

$D=\\{\,\\{v,x\\},\,\\{w,y\\},\,\\{z\\}\\}$,

$\bullet$

$f_{c}$ is of type product.

It holds that:

$\bullet$

$S_{1}:=\\{v,x\\}$ and $S_{2}:=\\{w,y\\}$ are optimal with cost $12$, whereas
$S_{3}:=\\{z\\}$ is non-optimal with cost $24$.

######  Example 4.

$\bullet$

${\cal E}=\\{w,x,y,z\\}$ with $c(w)=2$, $c(x)=3$, $c(y)=7$, $c(z)=8$.

$\bullet$

$D=\\{\,\\{w,y\\},\,\\{x,y\\},\,\\{z\\}\\}$,

$\bullet$

$f_{c}$ is of type bottleneck.

It holds that:

$\bullet$

$S_{1}:=\\{w,y\\}$ and $S_{2}:=\\{x,y\\}$ are optimal with cost $7$, whereas
$S_{3}:=\\{z\\}$ is non-optimal with cost $8$.

##  4 Generalized Definition of Regular/Reverse Set Upper/Lower Tolerances

In this section, we provide new definitions of single and set tolerances,
which apply to all elements / subsets. Note that the prime is used to
distinguish the new definitions from the existing ones.

Let $E\subseteq{\cal E}$.

$\displaystyle u^{\prime}_{{\cal P}}({E})$ $\displaystyle:=$
$\displaystyle\sup\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\mbox{for
each optimal $S^{\ast}$ for}\ {\cal P}\ $
$\displaystyle\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq
0,\ $ $\displaystyle\alpha=\sum_{l=1}^{k}\alpha_{l},\;S^{\ast}\ \mbox{is
optimal for}\ {\cal P}_{c_{{\vec{\alpha}},{E}}}\Big{\\}}.$
$\displaystyle\bar{u}^{\prime}_{{\cal P}}({E})$ $\displaystyle:=$
$\displaystyle\inf\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\exists\,\mbox{optimal
$S^{\ast}$ for}\ {\cal P}\ $
$\displaystyle\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),\;\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq
0,\ $ $\displaystyle\alpha=\sum_{l=1}^{k}\alpha_{l},\;S^{\ast}\ \mbox{is not
optimal for}\ {\cal P}_{c_{{\vec{\alpha}},{E}}}\Big{\\}}.$ $\displaystyle
l^{\prime}_{{\cal P}}({E})$ $\displaystyle:=$
$\displaystyle\sup\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle
0\leq\alpha_{1}<\delta(e_{1}),0\leq\alpha_{2}<\delta(e_{2}),\dots,0\leq\alpha_{k}$
$\displaystyle<\delta(e_{k}),\
\alpha=\sum_{l=1}^{k}\alpha_{l},{f_{c_{-\vec{\alpha},E}}}({\cal
P}_{c_{{-\alpha},{E}}})=f_{c}({\cal P})\\}.$
$\displaystyle\bar{l}^{\prime}_{{\cal P}}({E})$ $\displaystyle:=$
$\displaystyle\inf\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle\;0\leq\alpha_{1}<\delta(e_{1}),0\leq\alpha_{2}<\delta(e_{2}),\dots,0\leq\alpha_{k}$
$\displaystyle<\delta(e_{k}),\
\alpha=\sum_{l=1}^{k}\alpha_{l},{f_{c_{-\vec{\alpha},E}}}({\cal
P}_{c_{{-\alpha},{E}}})<f_{c}({\cal P})\\}.$

It holds that:

$\displaystyle u^{\prime}_{{\cal P}}({E})$ $\displaystyle:=$
$\displaystyle\max\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\mbox{for
each optimal $S^{\ast}$ for}\ {\cal P}\ $
$\displaystyle\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq
0,\ $ $\displaystyle\alpha=\sum_{l=1}^{k}\alpha_{l},S^{\ast}\ \mbox{is optimal
for}\ {\cal P}_{c_{{\vec{\alpha}},{E}}}\Big{\\}}$ $\displaystyle\mbox{if}\
u^{\prime}_{{\cal P}}({E})<\infty.$ $\displaystyle\bar{l}^{\prime}_{{\cal
P}}({E})$ $\displaystyle:=$
$\displaystyle\max\;\Big{\\{}\alpha\in\mathbb{R}\mathrel{\Big{|}}\exists\,\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}),$
$\displaystyle
0\leq\alpha_{1}<\delta(e_{1}),0\leq\alpha_{2}<\delta(e_{2}),\dots,0\leq\alpha_{k}$
$\displaystyle<\delta(e_{k}),\
\alpha=\sum_{l=1}^{k}\alpha_{l},{f_{c_{-\vec{\alpha},E}}}({\cal
P}_{c_{{-\alpha},{E}}})=f_{c}({\cal P})\\}$ $\displaystyle\mbox{if}\
l^{\prime}_{{\cal P}}({E})<\infty.$

Clearly, single elements are sets of cardinality one. We write for short:

$\displaystyle u^{\prime}_{{\cal P}}({e})$ $\displaystyle:=$ $\displaystyle
u^{\prime}_{{\cal P}}({\\{e\\}})$ $\displaystyle\bar{u}^{\prime}_{{\cal
P}}({e})$ $\displaystyle:=$ $\displaystyle\bar{u}^{\prime}_{{\cal
P}}({\\{e\\}})$ $\displaystyle l^{\prime}_{{\cal P}}({e})$ $\displaystyle:=$
$\displaystyle l^{\prime}_{{\cal P}}({\\{e\\}})$
$\displaystyle\bar{l}^{\prime}_{{\cal P}}({e})$ $\displaystyle:=$
$\displaystyle\bar{l}^{\prime}_{{\cal P}}({\\{e\\}})$

Applying the definitions to those sets of cardinality one, we obtain the
following new definitions of single tolerances:

$\displaystyle u^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}\mid\mbox{each opt.\ $S^{\ast}$
for}\ {\cal P}\ \mbox{is opt.\ for}\ {\cal P}_{c_{{\alpha},{e}}}\\}.$
$\displaystyle\bar{u}^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\inf\;\\{\alpha\in\mathbb{R}\mid\exists\,\mbox{opt.\ $S^{\ast}$
for}\ {\cal P}\ \mbox{not opt.\ for}\ {\cal P}_{c_{{\alpha},{e}}}\\}.$
$\displaystyle l^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}\mid{f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=f_{c}({\cal P})\\}.$
$\displaystyle\bar{l}^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\inf\;\\{\alpha\in\mathbb{R}\mid{f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})\\}.$

Furthermore, we have:

$\displaystyle u^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\max\;\\{\alpha\in\mathbb{R}\mid\mbox{each opt.\ $S^{\ast}$
for}\ {\cal P}\ \mbox{is opt.\ for}\ {\cal P}_{c_{{\alpha},{e}}}\\}\ $
$\displaystyle\mbox{if}\ u^{\prime}_{{\cal P}}({e})<\infty.$ $\displaystyle
l^{\prime}_{{\cal P}}({e})$ $\displaystyle=$
$\displaystyle\max\;\\{\alpha\in\mathbb{R}\mid{f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=f_{c}({\cal P})\\}\ \quad\mbox{if}\ l^{\prime}_{{\cal
P}}({e})<\infty.$

Clearly, it holds that:

######  Remark 1.

(a)

$\bar{u}^{\prime}_{{\cal P}}({E})\leq u^{\prime}_{{\cal P}}({E})$.

(b)

$\bar{l}^{\prime}_{{\cal P}}({E})\leq l^{\prime}_{{\cal P}}({E})$.

(c)

$u^{\prime}_{{\cal P}}({\bar{E}})\leq u^{\prime}_{{\cal P}}({E})$ for
$\bar{E}\subseteq E$.

(d)

$\bar{u}^{\prime}_{{\cal P}}({E})\leq\bar{u}^{\prime}_{{\cal P}}({\bar{E}})$
for $\bar{E}\subseteq E$.

(e)

$l^{\prime}_{{\cal P}}({\bar{E}})\leq l^{\prime}_{{\cal P}}({E})$ for
$\bar{E}\subseteq E$.

(f)

$\bar{l}^{\prime}_{{\cal P}}({E})\leq\bar{l}^{\prime}_{{\cal P}}({\bar{E}})$
for $\bar{E}\subseteq E$.

(g)

All new definitions are independent of a given optimal solution.

##  5 Consistency of Generalized Definition with Original Definition

In this section, we show that all generalized definitions are consistent with
the original ones, i.e., the original definitions are still valid.

######  Theorem 7.

Let ${\cal P}$ be an instance, where $f_{c}$ is of type sum, product, or
bottleneck.

(a)

Let $e\in UTE_{{\cal P}}$. Then $u^{\prime}_{{\cal
P}}({e})=\bar{u}^{\prime}_{{\cal P}}({e})=u_{{\cal P}}({e})$ holds.

(b)

Let $e\in LTE_{{\cal P}}$. Then $l^{\prime}_{{\cal
P}}({e})=\bar{l}^{\prime}_{{\cal P}}({e})=l_{{\cal P}}({e})$ holds.

(c)

$u^{\prime}_{{\cal P}}({E})=u_{{\cal P}}({E})$ for $E\in UTS_{{\cal P}}$.

(d)

$\bar{u}^{\prime}_{{\cal P}}({E})=u_{{\cal P}}({E})$ for $E\in UTS_{{\cal
P}}$.

(e)

$l^{\prime}_{{\cal P}}({E})=l_{{\cal P}}({E})$ for $E\in LTS_{{\cal P}}$.

(f)

$\bar{l}^{\prime}_{{\cal P}}({E})=l_{{\cal P}}({E})$ for $E\in LTS_{{\cal
P}}$.

Proof.

(a)

Let $e\in UTE_{{\cal P}}$, i.e., $e$ lies inside at least one optimal
solution.

$u^{\prime}_{{\cal P}}({e})\leq u_{{\cal P}}({e})$ and
$\bar{u}^{\prime}_{{\cal P}}({e})\leq u_{{\cal P}}({e})$ hold by definition.

For showing $u^{\prime}_{{\cal P}}({e})\geq u_{{\cal P}}({e})$ and
$\bar{u}^{\prime}_{{\cal P}}({e})\geq u_{{\cal P}}({e})$, let $S^{\ast}$ be an
arbitrary optimal solution of ${\cal P}$. We distinguish between two cases:

(A)

$e\in S^{\ast}$.

By definition, $S^{\ast}$ remains optimal if $c(e)$ is increased by $u_{{\cal
P}}({e})$ and does not remain optimal if $c(e)$ is increased by more than
$u_{{\cal P}}({e})$.

(B)

$e\notin S^{\ast}$.

$S^{\ast}$ remains optimal if $c(e)$ is increased by an arbitrary $\beta>0$ ,
in particular by $\beta:=u_{{\cal P}}({e})$.

It follows that $u^{\prime}_{{\cal P}}({e})\geq u_{{\cal P}}({e})$, and
$\bar{u}^{\prime}_{{\cal P}}({e})\geq u_{{\cal P}}({e})$, and thus
$u^{\prime}_{{\cal P}}({e})=\bar{u}^{\prime}_{{\cal P}}({e})=u_{{\cal
P}}({e})$.

(b)

Let $e\in LTE_{{\cal P}}$, and let $S^{\ast}$ be an optimal solution with
$e\in{\cal E}\setminus S^{\ast}$. We distinguish between three cases:

(A)

$f_{c}$ is of type sum.

By Theorem 2(a) it remains to be shown:

$\displaystyle l^{\prime}_{{\cal P}}({e})\;=\;\bar{l}^{\prime}_{{\cal
P}}({e})\;=\;f_{c}(D_{+}(e))-f_{c}({\cal P}).$

We distinguish between two subcases:

(i)

$D_{+}(e)=\emptyset$ (i.e. there is no feasible solution containing $e$).

It holds that $l^{\prime}_{{\cal P}}({e})=\bar{l}^{\prime}_{{\cal
P}}({e})=l_{{\cal P}}({e})=\infty$.

(ii)

$D_{+}(e)\not=\emptyset$.

The assertion holds, as decreasing $c(e)$ by $f_{c}(D_{+}(e))-f_{c}({\cal P})$
keeps the objective value the same, and decreasing it by
$f_{c}(D_{+}(e))-f_{c}({\cal P})+\alpha$ for each $\alpha>0$ decreases the
objective value.

(B)

$f_{c}$ is of type product.

By Theorem 2(b) it remains to be shown:

$\displaystyle l^{\prime}_{{\cal P}}({e})\;=\;\bar{l}^{\prime}_{{\cal
P}}({e})\;=\;\frac{f_{c}(D_{+}(e))-f_{c}({\cal P})}{f_{c}(D_{+}(e))}\cdot
c(e).$

We distinguish between two subcases:

(i)

$D_{+}(e)=\emptyset$.

It holds that $l^{\prime}_{{\cal P}}({e})=\bar{l}^{\prime}_{{\cal
P}}({e})=l_{{\cal P}}({e})=\infty$.

(ii)

$D_{+}(e)\not=\emptyset$.

The assertion holds, as decreasing $c(e)$ by
$\frac{f_{c}(D_{+}(e))-f_{c}({\cal P})}{f_{c}(D_{+}(e))}\cdot c(e)$ keeps the
objective value the same, and decreasing it by
$\frac{f_{c}(D_{+}(e))-f_{c}({\cal P})}{f_{c}(D_{+}(e))}\cdot c(e)+\alpha$ for
each $\alpha>0$ decreases the objective value.

(C)

$f_{c}$ is of type bottleneck.

We have two possible cases:

i)

There does not exist an $\alpha>0~{}$ with ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})=c^{\ast}$.

It holds that $g(e)\geq c^{\ast}$. In this case, the lower tolerances
according to all three definitions are $\infty$.

ii)

There exists an $\alpha>0~{}$ with ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})$.

It holds that $g(e)<c^{\ast}$. By the monotony of an objective function of
type bottleneck in the cost of $e$, there must be a $\beta\in\mathbb{R}$ with
$0<\beta<\alpha~{}$ and a feasible solution $S$ so that the following holds
for all $\gamma,\theta$ with $0\leq\gamma<\beta<\theta~{}$:

$\displaystyle{f_{c_{-\beta,e}}}(S)$ $\displaystyle=$
$\displaystyle{f_{c_{-\beta,e}}}(S^{\ast})\;=\;f_{c}(S^{\ast}),$
$\displaystyle{f_{c_{-\theta,e}}}(S)$ $\displaystyle<$
$\displaystyle{f_{c_{-\theta,e}}}(S^{\ast})\;=\;f_{c}(S^{\ast}),$
$\displaystyle{f_{c_{-\gamma,e}}}(S)$ $\displaystyle>$
$\displaystyle{f_{c_{-\gamma,e}}}(S^{\ast})\;=\;f_{c}(S^{\ast}).$

It follows:

$\displaystyle\beta$ $\displaystyle=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}\mid S^{\ast}\ \mbox{is optimal
for}\ {\cal P}_{c_{{-\alpha},{e}}}\\}$ $\displaystyle=$
$\displaystyle\sup\;\\{\alpha\in\mathbb{R}\mid{f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=f_{c}({\cal P})\\}.$ $\displaystyle=$
$\displaystyle\inf\;\\{\alpha\in\mathbb{R}\mid{f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})\\}.$

Thus, the three definitions of lower tolerance lead to the same value $\beta$.

(c),(d)

Let $E=\\{e_{1},e_{2},\dots,e_{k}\\}\in UTS_{{\cal P}}$.

$u^{\prime}_{{\cal P}}({E})\leq u_{{\cal P}}({E})$ and
$\bar{u}^{\prime}_{{\cal P}}({E})\leq u_{{\cal P}}({E})$ hold by definition.

For showing $u^{\prime}_{{\cal P}}({E})\geq u_{{\cal P}}({E})$, and
$\bar{u}^{\prime}_{{\cal P}}({E})\geq u_{{\cal P}}({E})$, let $S^{\ast}$ be an
optimal solution of ${\cal P}$.

We distinguish between two cases:

(A)

$E\subseteq S^{\ast}$.

By definition, $S^{\ast}$ remains optimal if there are
$\alpha_{1},\alpha_{2},\dots,\alpha_{k}\geq 0$ with sum $u_{{\cal P}}({E})$ so
that $c(e_{l})$ is increased by $\alpha_{l}$ for $l=1,2,\dots,k$.

(B)

$E\nsubseteq S^{\ast}$.

Then there exists an $t\in\\{1,2,\dots,k\\}$ such that $e_{t}\notin S^{\ast}$.
$S^{\ast}$ remains optimal if $c(e_{t})$ is increased by an arbitrary
$\beta>0$. It follows that $u^{\prime}_{{\cal P}}({E})=u_{{\cal
P}}({E})=\infty$.

$u^{\prime}_{{\cal P}}({E})\geq u_{{\cal P}}({E})$ and
$\bar{u}^{\prime}_{{\cal P}}({E})\geq u_{{\cal P}}({E})$ follow.

(e),(f)

Let $E=\\{e_{1},e_{2},\dots,e_{k}\\}\in LTS_{{\cal P}}$, i.e., it exists an
optimal solution $S^{\ast}$ with $E\subseteq{\cal E}\setminus S^{\ast}$.
Because of that, when decreasing $c(e_{i})$ by $\alpha_{i}>0$ for
$i=1,2,\dots,k$, making $S^{\ast}$ non-optimal corresponds to decreasing the
objective value. Both assertions follow. ∎

##  6 Extension of formulas and bounds

In this section, we show which exact formulas and which bounds for the
original definitions still hold for the generalized case.

######  Theorem 8.

(a)

Let $e\in{\cal E}\setminus UTE_{{\cal P}}$. Then $u^{\prime}_{{\cal
P}}({e})=\bar{u}^{\prime}_{{\cal P}}({e})=\infty$ holds.

(b)

Theorem 1 cannot be generalized for any of the objective functions of type
sum, product, bottleneck.

Proof. The case $e\in UTE_{{\cal P}}$ is covered by Theorem 7(a).

Let $e\in{\cal E}\setminus UTE_{{\cal P}}$, i.e., $e$ lies outside each
optimal solution.

(a)

Each optimal solution remains optimal if $c(e)$ is increased by an arbitrary
$\beta>0$. It follows that $u^{\prime}_{{\cal P}}({e})=\bar{u}^{\prime}_{{\cal
P}}({e})=\infty$.

(b)

By (a), the formulas of Theorem 1 only hold for ${\cal E}\setminus UTE_{{\cal
P}}$ if the right-hand terms of Theorem 1(a), (b), (c) are $\infty$. However,
each of these terms can only be $\infty$ if the term $f_{c}(D_{-}(e))$, equals
$\infty$, and this is only the case if each feasible solution contains $e$.
With other words, the formulas of Theorem 1 do not hold in general. ∎

######  Theorem 9.

Let $e\in{\cal E}\setminus LTE_{{\cal P}}$.

(a)

Then $l^{\prime}_{{\cal P}}({e})=\bar{l}^{\prime}_{{\cal
P}}({e})\in\\{0,\infty\\}$ holds, where in the case that $f_{c}$ is of type
sum, product, the lower tolerance is always $0$.

(b)

Theorem 2 holds for each of the objective functions of type sum, product,
bottleneck.

Proof. (a), (b) The case $e\in LTE_{{\cal P}}$ is covered by Theorem 7(b).

Let $e\in{\cal E}\setminus LTE_{{\cal P}}=OPT_{{\cal P}}$, i.e., $e$ lies
inside each optimal solution. We distinguish between three cases:

(A)

$f_{c}$ is of type sum.

Let $\alpha>0$ be arbitrary. Then it holds that ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=f_{c}({\cal P})-\alpha$. Thus, decreasing $c(e)$ by
$\alpha$ decreases the objective value. $l^{\prime}_{{\cal
P}}({e})=\bar{l}^{\prime}_{{\cal P}}({e})=0$ follows.

As $e$ lies in each optimal solution, it follows:

$\displaystyle l^{\prime}_{{\cal P}}({e})\;=\;\bar{l}^{\prime}_{{\cal
P}}({e})\;=\;0\;=\;f_{c}(D_{+}(e))-f_{c}({\cal P}).$

Thus, Theorem 2(a) holds.

(B)

$f_{c}$ is of type product.

Let $\alpha>0$ be arbitrary. Then it holds that ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=f_{c}({\cal P})\cdot\frac{c(e)-\alpha}{c(e)}$. As all
elements have positive cost, decreasing $c(e)$ by $\alpha$ decreases the
objective value. $l^{\prime}_{{\cal P}}({e})=\bar{l}^{\prime}_{{\cal
P}}({e})=0$ follows.

As $e$ lies in each optimal solution, it follows:

$\displaystyle l^{\prime}_{{\cal P}}({e})\;=\;\bar{l}^{\prime}_{{\cal
P}}({e})\;=\;0\;=\;\frac{f_{c}(D_{+}(e))-f_{c}({\cal
P})}{f_{c}(D_{+}(e))}\cdot c(e).$

Thus, Theorem 2(b) holds.

(C)

$f_{c}$ is of type bottleneck.

Clearly, $c(e)\leq c^{\ast}~{}$ holds. We distinguish between two subcases:

i)

There does not exist an $\alpha>0~{}$ with ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})$.

It follows that $l^{\prime}_{{\cal P}}({e})=\bar{l}^{\prime}_{{\cal
P}}({e})=\infty$. It holds that $g(e)\geq c^{\ast}$, and thus, Theorem 2(c)
follows in this case.

ii)

There exists an $\alpha>0~{}$ with ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})$.

If $c(e)<c^{\ast}$ holds, it follows that ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})=c^{\ast}$ for all $\alpha>0$, which conflicts with the
assumption. Therefore, it holds that $c(e)=c^{\ast}~{}$ and for all
$\alpha>0~{}$ that ${f_{c_{-\alpha,e}}}({\cal
P}_{c_{{-\alpha},{e}}})<f_{c}({\cal P})$. It follows that $l^{\prime}_{{\cal
P}}({e})=\bar{l}^{\prime}_{{\cal P}}({e})=0$.

It holds that $g(e)<c^{\ast}$. Because of that and because of $c(e)=c^{\ast}$,
Theorem 2(c) follows in this case. ∎

The following theorem shows that Theorem 3 applied to the newly define regular
set upper tolerance can only be partly generalized to arbitrary
$E\subseteq{\cal E}$.

######  Theorem 10.

Let ${\cal P}$ be an instance and
$E=\\{e_{1},e_{2},\dots,e_{k}\\}\subseteq{\cal E}$. Then the following holds:

(a)

$\max_{l=1}^{k}\,\\{u^{\prime}_{{\cal P}}({e_{l}})\\}\;\leq\;u^{\prime}_{{\cal
P}}({E})$.

(b)

If $f_{c}$ is of type sum, product or bottleneck, $u^{\prime}_{{\cal
P}}({E})\;\leq\;\sum_{l=1}^{k}u^{\prime}_{{\cal P}}({e_{l}})$ does _not_
always hold.

(c)

If $f_{c}$ is of type bottleneck, $\sum_{l=1}^{k}u^{\prime}_{{\cal
P}}({e_{l}})\;\leq\;u^{\prime}_{{\cal P}}({E})$.

Proof.

(a)

This follows directly from Remark 1(c).

(b)

We distinguish between three cases.

(A)

$f_{c}$ is of type sum.

Consider Example 2. Let $E=\\{v,w\\}$, $e_{1}=v$, $e_{2}=w$, It holds that
$u^{\prime}_{{\cal P}}({v})=u^{\prime}_{{\cal P}}({w})=0$ and
$u^{\prime}_{{\cal P}}({E})=2$ as both $S_{1}$ and $S_{2}$ remain optimal, if
$c(v)$ and $c(w)$ are increased by $1$ at the same time. Thus,
$u^{\prime}_{{\cal P}}({\\{v,w\\}})=2>0=u^{\prime}_{{\cal
P}}({v})+u^{\prime}_{{\cal P}}({w})$ holds.

(B)

$f_{c}$ is of type product.

Consider Example 3. Let $E=\\{v,w\\}$, $e_{1}=v$, $e_{2}=w$, It holds that
$u^{\prime}_{{\cal P}}({v})=u^{\prime}_{{\cal P}}({w})=0$ and
$u^{\prime}_{{\cal P}}({E})=5$ as both $S_{1}$ and $S_{2}$ remain optimal, if
$c(v)$ is increased by $2$ and $c(w)$ is increased by $3$ at the same time.
Thus, $u^{\prime}_{{\cal P}}({\\{v,w\\}})=5>0=u^{\prime}_{{\cal
P}}({v})+u^{\prime}_{{\cal P}}({w})$ holds.

(C)

$f_{c}$ is of type bottleneck.

Consider Example 4. Let $E=\\{w,x\\}$, $e_{1}=w$, $e_{2}=x$. It holds that
$u^{\prime}_{{\cal P}}({w})=5$, $u^{\prime}_{{\cal P}}({x})=4$,
$u^{\prime}_{{\cal P}}({E})=11$ as both $S_{1}$ and $S_{2}$ remain optimal, if
$c(w)$ is increased by $6$ and $c(x)$ is increased by $5$ at the same time.
Thus, $u^{\prime}_{{\cal P}}({\\{w,x\\}})=11>9=u^{\prime}_{{\cal
P}}({w})+u^{\prime}_{{\cal P}}({x})$ holds.

(c)

Trivially, the inequality is true if $u^{\prime}_{{\cal P}}({E})=\infty$. If
$\sum_{l=1}^{k}u^{\prime}_{{\cal P}}({e_{l}})=\infty$ holds, then it also
holds that $\max_{l=1}^{k}\,\\{u^{\prime}_{{\cal P}}({e_{l}})\\}=\infty$. It
follows from (a) that $u^{\prime}_{{\cal P}}({E})=\infty$, and the inequality
is also true. In the following let both terms $u^{\prime}_{{\cal P}}({E})$ and
$\sum_{l=1}^{k}u^{\prime}_{{\cal P}}({e_{l}})$ be not equal $\infty$.

Let $S^{\ast}$ be an arbitrary optimal solution of ${\cal P}$. Let
$\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,$ $\alpha_{k})$ and
$\alpha_{l}=u_{{\cal P}}({e_{l}})<\infty$ for $l=1,2,\dots,k$. We distinguish
between two cases.

(A)

$E\cap S^{\ast}=\emptyset$.

Then it holds for each feasible solution $S$:

$\displaystyle{f_{c_{\vec{\alpha},E}}}(S^{\ast})\;=\;f_{c}(S^{\ast})\;\leq\;f_{c}(S)\;\leq\;{f_{c_{\vec{\alpha},E}}}(S).$

(B)

$E\cap S^{\ast}\not=\emptyset$.

Choose $t\in\\{1,2,\dots,k\\}$ such that

$\displaystyle c(e_{t})+\alpha_{t}$ $\displaystyle=$
$\displaystyle\max_{l=1,e_{l}\in S^{\ast}}^{k}\\{c(e_{l})+\alpha_{l}\\}$ (4)

Note that $t$ exists because of $E\cap S^{\ast}\not=\emptyset$ and
$\alpha_{l}=u_{{\cal P}}({e_{l}})<\infty$ for $l=1,2,\dots,k$. Then it holds
for each feasible solution $S$:

$\displaystyle{f_{c_{\vec{\alpha},E}}}(S^{\ast})$
$\displaystyle\;=\;{f_{c_{\alpha_{t},e_{t}}}}(S^{\ast})$
$\displaystyle\mbox{because of Eq.~{}\eqref{max_rel}},$
$\displaystyle\;\leq\;{f_{c_{\alpha_{t},e_{t}}}}(S),$
$\displaystyle\mbox{because of $\alpha_{t}=u_{{\cal P}}({e_{t}})$},$
$\displaystyle\;\leq\;{f_{c_{\vec{\alpha},E}}}(S).$

It follows that $\sum_{l=1}^{k}u_{{\cal P}}({e_{l}})\leq u_{{\cal P}}({E})$. ∎

The following theorem shows that Theorem 4 applied to the newly define regular
set lower tolerance can be generalized to arbitrary $E\in{\cal E}$.

######  Theorem 11.

Let ${\cal P}$ be an instance and $E=\\{e_{1},e_{2},\dots,e_{k}\\}\in{\cal
E}$. Then the following holds:

(a)

$\bar{u}^{\prime}_{{\cal P}}({E})\leq\;\min_{l=1}^{k}\,\\{u^{\prime}_{{\cal
P}}({e_{l}})\\}$.

(b)

If $f_{c}$ is of type sum or bottleneck, $\bar{u}^{\prime}_{{\cal
P}}({E})\;=\;\min_{l=1}^{k}\\{u^{\prime}_{{\cal P}}({e_{l}})\\}$.

(c)

If $f_{c}$ is of product,
$\left(\sqrt[k]{\min_{l=1}^{k}\left\\{\frac{u^{\prime}_{{\cal
P}}({e_{l}})}{c(e_{l})}\right\\}+1}-1\right)\cdot\min_{l=1}^{k}\,\\{c(e_{l})\\}\;\leq\;\bar{u}^{\prime}_{{\cal
P}}({E})$.

Proof.

(a)

This follows directly from Remark 1(d).

(b)

By (a), it remains to be shown that $\bar{u}^{\prime}_{{\cal
P}}({E})\geq\;\min_{l=1}^{k}\,\\{\bar{u}^{\prime}_{{\cal P}}({e_{l}})\\}$.

Let $S^{\ast}$ be an optimal solution corresponding to the definion of
$\bar{u}^{\prime}_{{\cal P}}({E})$. To make $S^{\ast}$ non-optimal by
increasing some of the costs $c(e_{i})$ for $i=1,2,\dots,k$ with infimum sum
of increases, we can restrict to the case that only those $c(e_{i})$ are
increased such that $e_{i}\in S^{\ast}$ and the other $c(e_{i})$ are not
increased. Then for $\bar{E}:=E\cap S^{\ast}$ it holds that $\bar{E}\in
UTS_{{\cal P}}$. By Theorem 4(b), it follows:

$\displaystyle\bar{u}^{\prime}_{{\cal P}}({E})\;=\;\bar{u}^{\prime}_{{\cal
P}}({\bar{E}})\;=\;\min_{l=1,e_{l}\in\bar{E}}^{k}\\{u^{\prime}_{{\cal
P}}({e_{l}})\\}\;\geq\;\min_{l=1}^{k}\\{u^{\prime}_{{\cal P}}({e_{l}})\\}.$

(c)

Analogously to (b), it holds for $\bar{E}:=E\cap S^{\ast}$ that $\bar{E}\in
UTS_{{\cal P}}$. By Theorem 4(b), it follows:

$\displaystyle\bar{u}^{\prime}_{{\cal P}}({E})\;=\;\bar{u}^{\prime}_{{\cal
P}}({\bar{E}})$ $\displaystyle=$
$\displaystyle\left(\sqrt[k]{\min_{l=1,e_{l}\in\bar{E}}^{k}\left\\{\frac{u_{{\cal
P}}({e_{l}})}{c(e_{l})}\right\\}+1}-1\right)\cdot\min_{l=1,e_{l}\in\bar{E}}^{k}\,\\{c(e_{l})\\}$
$\displaystyle\geq$
$\displaystyle\left(\sqrt[k]{\min_{l=1}^{k}\left\\{\frac{u_{{\cal
P}}({e_{l}})}{c(e_{l})}\right\\}+1}-1\right)\cdot\min_{l=1}^{k}\,\\{c(e_{l})\\}.\hfill\qed$

The following theorem shows that Theorem 5 applied to the newly define regular
set lower tolerance can be generalized to arbitrary $E\in{\cal E}$.

######  Theorem 12.

Let ${\cal P}$ be an instance and $E=\\{e_{1},e_{2},\dots,e_{k}\\}\in{\cal
E}$. Then the following holds:

(a)

$\max_{l=1}^{k}\,\\{l^{\prime}_{{\cal P}}({e_{l}})\\}\;\leq\;l^{\prime}_{{\cal
P}}({E})\;\leq\;\sum_{l=1}^{k}l^{\prime}_{{\cal P}}({e_{l}})$.

(b)

If $f_{c}$ is of type bottleneck, $l^{\prime}_{{\cal
P}}({E})\;=\;\sum_{l=1}^{k}l^{\prime}_{{\cal P}}({e_{l}})$.

Proof.

(a)

We show the claimed inequalities.

$\bullet$

$\max_{l=1}^{k}\,\\{l^{\prime}_{{\cal P}}({e_{l}})\\}\leq l^{\prime}_{{\cal
P}}({E})$.

This follows directly from Remark 1(e).

$\bullet$

$l^{\prime}_{{\cal P}}({E})\leq\sum_{l=1}^{k}l^{\prime}_{{\cal P}}({e_{l}})$.

Trivially, the inequality is true if $\sum_{l=1}^{k}l^{\prime}_{{\cal
P}}({e_{l}})=$ $\infty$. In the following let $\sum_{l=1}^{k}l^{\prime}_{{\cal
P}}({e_{l}})$ $\not=\infty$.

Assume that $l^{\prime}_{{\cal P}}({E})>\sum_{l=1}^{k}l^{\prime}_{{\cal
P}}({e_{l}})$. Choose $\alpha\in\mathbb{R}$ with
$\sum_{l=1}^{k}l^{\prime}_{{\cal P}}({e_{l}})<\alpha\leq l^{\prime}_{{\cal
P}}({E})$, $\alpha=\sum_{l=1}^{k}\alpha_{l}$,
$\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k})$ and
$0\leq\alpha_{l}<\delta(e_{l})$ for $l=1,2,\dots,k$ so that
${f_{c_{-\vec{\alpha},E}}}({\cal P}_{c_{{-\alpha},{E}}})\;=\;f_{c}({\cal P})$
holds. Then a $t\in\\{1,2,\dots,k\\}$ exists with
$\alpha_{t}>l^{\prime}_{{\cal P}}({e_{t}})$. By the definition of
$l^{\prime}_{{\cal P}}({e_{t}})$, we receive a contradiction. The assertion
follows.

(b)

By (a), it remains to be shown that $\sum_{l=1}^{k}l^{\prime}_{{\cal
P}}({e_{l}})\leq l^{\prime}_{{\cal P}}({E})$.

Trivially, the inequality is true if $l_{{\cal P}}({E})=\infty$. If
$\sum_{l=1}^{k}l_{{\cal P}}({e_{l}})=\infty$ holds, then it also holds that
$\max_{l=1}^{k}\,\\{l_{{\cal P}}({e_{l}})\\}=\infty$. From (a) it follows that
$l_{{\cal P}}({E})=\infty$, and the inequality is also true. In the following
let both terms $l_{{\cal P}}({E})$ and $\sum_{l=1}^{k}l_{{\cal P}}({e_{l}})$
be not equal $\infty$.

Let $\alpha\geq 0$ with
$\alpha=\sum_{l=1}^{k}\alpha_{l},\;\vec{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k})$
and $\alpha_{l}=l_{{\cal P}}({e_{l}})$ for $l=1,2,\dots,k$. By Theorem 9(b),
$l_{{\cal P}}({e_{l}})=c(e_{l})-c^{\ast}\not=\infty$ holds. It follows:

$\displaystyle{f_{c_{-\vec{\alpha},E}}}({\cal
P}_{c_{{-\alpha},{E}}})\;\geq\;\min\\{c^{\ast},\min_{l=1}^{k}\\{c(e_{l})-(c(e_{l})-c^{\ast})\\}\\}\;=\;c^{\ast}\;=\;f_{c}({\cal
P}).$

Equality and the assertion follows. ∎

The following theorem shows that Theorem 6 applied to the newly define regular
set lower tolerance can be generalized to arbitrary $E\in{\cal E}$.

######  Theorem 13.

Let ${\cal P}$ be an instance and $E=\\{e_{1},e_{2},\dots,e_{k}\\}\in{\cal
E}$. Then the following holds:

(a)

$\bar{l}^{\prime}_{{\cal P}}({E})\;\leq\;\min_{l=1}^{k}\,\\{l^{\prime}_{{\cal
P}}({e_{l}})\\}$.

(b)

If $f_{c}$ is of type sum or product, $\bar{l}^{\prime}_{{\cal
P}}({E})\;=\;\min_{l=1}^{k}\,\\{l^{\prime}_{{\cal P}}({e_{l}})\\}$.

Proof.

(a)

This follows directly from Remark 1(f).

(b)

By (a) it remains to be shown that $\min_{l=1}^{k}\,\\{l^{\prime}_{{\cal
P}}({e_{l}})\\}\leq\bar{l}^{\prime}_{{\cal P}}({E})$.

Trivially, the inequality is true if $\bar{l}^{\prime}_{{\cal
P}}({E})=\infty$. In the following let $\bar{l}^{\prime}_{{\cal
P}}({E})\not=\infty$.

Assume that $\min_{l=1}^{k}\,\\{l^{\prime}_{{\cal
P}}({e_{l}})\\}>\bar{l}^{\prime}_{{\cal P}}({E})$.

We distinguish between two cases:

(A)

There is at least one $t\in\\{1,2,\dots,k\\}$ such that $e_{t}$ lies in an
optimal solution.

As for an objective function of type sum or product, decreasing the cost of an
element of an optimal solution by any $\epsilon$ decreases the objective
value, it follows:

$\displaystyle 0\;=\;\min_{l=1}^{k}\,\\{l^{\prime}_{{\cal
P}}({e_{l}})\\}\;>\;\bar{l}^{\prime}_{{\cal P}}({E})\;\geq\;0.$

This is a contradiction, and the assertion follows.

(B)

There is no $t\in\\{1,2,\dots,k\\}$ such that $e_{t}$ lies in an optimal
solution.

It follows that $\\{e_{1},e_{2},\dots,e_{k}\\}\subseteq LTS_{{\cal P}}$. The
assertion follows by Theorem 6(b) and by Theorem 7(f). ∎

##  7 Alternative Definitions – Discussion

The newly defined set tolerances have in common that they no longer depend on
a given optimal solution and are defined for all subsets of the ground set
${\cal E}$. They have three different concepts. The regular set upper
tolerance considers all optimal solutions (concept I), the reverse set upper
tolerance considers at least one optimal solution (concept II), and the
(regular and reverse) set lower tolerance consider the objective value
(concept III).

In this section we aim to motivate why we choose the corresponding concept for
the new definitions of set tolerances. Theoretically, for each of the four
definitions, we could use each of the three concepts.

Regular Set Upper Tolerance

In the current new definition concept I is used.

Concept II is not reasonable, as then in Example 4 the single upper tolerance
of $w$ would be $\infty$, but according to the original definitions it is $5$.
Concept III is not reasonable, as then in Example 1 the single upper tolerance
of $w$ would be $0$, but according to the original definition it is $2$.

Reverse Set Upper Tolerance

In the current new definition concept II is used.

Analogously to the regular set upper tolerance, concept I is not reasonable,
as in Example 4 the single upper tolerance of $w$ would be $\infty$, and
concept III is not reasonable, as in Example 1 the single upper tolerance of
$w$ would be $0$.

Regular Set Lower Tolerance

In the current new definition concept III is used.

Concept I is not reasonable, as then in Example 4 the single lower tolerance
of $y$ would be $4$, which is neither $c(y)-c^{\ast}=0$ nor $\infty$. Thus,
Theorem 2(c) would no longer hold. Concept II is not reasonable, as then in
Example 2 the single lower tolerance of $v$ would be $\infty$, which is not
$f_{c}(D_{+}(v))-f_{c}({\cal P})=0$. Thus, Theorem 2(a) would no longer hold.

Reverse Set Lower Tolerance

In the current new definition concept III is used.

Analogously to the regular set lower tolerance, concept I is not reasonable,
as in Example 4 the single lower tolerance of $y$ would be $4$, and concept II
is not reasonable, as in Example 2 the single lower tolerance of $v$ would be
$\infty$.

## Conclusions and Future Work

In this work we have generalized the definition and extended the theory of set
tolerances to all possible single elements / subsets. We have shown that these
generalized definitions are consistent with the original ones and which
computation formulas and bounds hold for the extended definitions.

We hope that using this extended theory of set tolerances, (heuristical and
exact) algorithms will become more effective and easier to create.

Another direction of future work would be a further extension where both
increases and decreases are considered in parallel, i.e., a mixture of upper
and lower tolerances.

## Acknowledgement

This work was supported by the Swedish Research Council grant 2022-04535.

## References

  * [1] R. Germs, B. Goldengorin, and M. Turkensteen.  Lower tolerance-based branch and bound algorithms for the ATSP.  Computers and Operations Research, 39(2):291–298, 2012.
  * [2] B. Goldengorin, G. Jäger, and P. Molitor.  Tolerances applied in combinatorial optimization.  Journal of Computer Science, 2(9):716–734, 2006.
  * [3] K. Helsgaun.  An effective implementation of the Lin-Kernighan traveling salesman heuristic.  European Journal of Operational Research, 126(1):106–130, 2000\.
  * [4] G. Jäger, C. Dong, B. Goldengorin, P. Molitor, and D. Richter.  A backbone based TSP heuristic for large instances.  Journal of Heuristics, 20(1):107–124, 2014.
  * [5] G. Jäger and M. Turkensteen.  Extending single tolerances to set tolerances.  Discrete Applied Mathematics, 247:197–215, 2018.
  * [6] G. Jäger and M. Turkensteen.  Assessing the effect of multiple cost changes using reverse set tolerances.  Discrete Applied Mathematics, 2023.  Accepted.
  * [7] M. Turkensteen, D. Ghosh, B. Goldengorin, and G. Sierksma.  Tolerance-based branch and bound algorithms for the ATSP.  European Journal of Operational Research, 189(3):775–788, 2008\.
  * [8] M. Turkensteen and G. Jäger.  Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems.  Theoretical Computer Science, 937:1–21, 2022.