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

From MaRDI portal





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
    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
    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

    Identifiers