Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? (Q701961)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? |
scientific article |
Statements
Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? (English)
0 references
17 January 2005
0 references
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).
0 references
optimization
0 references
interval data
0 references
Pareto set
0 references
optimal solutions
0 references
spanning tree
0 references
perfect matching
0 references
travelling salesman
0 references
linear programming
0 references