Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? (Q701961)

The author studies an optimization problem of the form \(\min_{x\in X}f(x,c),\) \(X\) finite, where \(c\) is a vector of parameters bounded by \(c\in[\underline c,\overline c]\). She considers several ways how to define the set of optimal solutions in this case: \[ \begin{multlined}{\tilde X}_{\leq}=\{x^*\in X \mid \text{ no } x\in X \text{ satisfies } f(x,\underline c)\leq f(x^*,\underline c), f(x,\overline c)\leq f(x^*,\overline c),\\ \text{ with at least one inequality being strict}\},\end{multlined} \] \[ {\tilde X}_<=\{x^*\in X \mid \text{ no } x\in X \text{ satisfies } f(x,\overline c)<f(x^*,\underline c)\}, \] \[ W=\{x^*\in X \mid f(x^*,c)=\min_{x\in X}f(x,c) \text{ for some } c\in[\underline c,\overline c]\}, \] \[ S=\{x^*\in X \mid f(x^*,c)=\min_{x\in X}f(x,c) \text{ for each } c\in[\underline c,\overline c]\}. \] It is proved that \(S\subseteq {\tilde X}_{\leq}\subseteq W\subseteq {\tilde X}_<\) for all four optimization problems considered (spanning tree, perfect matching, travelling salesman, linear programming).