Stability analysis in discrete optimization involving generalized addition operations

DOI10.1007/S10957-015-0709-9zbMATH Open1327.90323OpenAlexW2105598547MaRDI QIDQ896189FDOQ896189

Authors V. V. Chistyakov, Panos M. Pardalos 

Publication date 14 December 2015

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.4242

zbMATH Keywords

objective functionoptimal solutionoptimization problemgeneralized additionstability interval

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Sensitivity, stability, parametric optimization (90C31)

Abstract: The paper addresses the tolerance approach to the sensitivity analysis of optimal solutions to the nonlinear optimization problem of the form ${\displaystyle }$mbox{$$quad overquad $SinmathcalS$,}${\displaystyle }$ where $mathcalS$ is a collection of nonempty subsets of a finite set $X$ such that the union of $mathcalS$ is $X$ and the intersection of $mathcalS$ 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.

Recommendations

• Some concepts of stability analysis in combinatorial optimization
• Stability of separable discrete optimization problems
• Some Basics on Tolerances
• Research of stability of vector problems of discrete optimization with different principles of optimality
• scientific article; zbMATH DE number 5172344

Cites Work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3155055 (Why is no real title available?)
• scientific article; zbMATH DE number 41606 (Why is no real title available?)
• scientific article; zbMATH DE number 3634009 (Why is no real title available?)
• scientific article; zbMATH DE number 1114459 (Why is no real title available?)
• scientific article; zbMATH DE number 6181170 (Why is no real title available?)
• scientific article; zbMATH DE number 969937 (Why is no real title available?)
• A general approach to the study of the stability of solutions in discrete optimization problems
• A note on Arc tolerances in sparse shortest-path and network flow problems
• Arc tolerances in shortest path and network flow problems
• Calculation of stability radii for combinatorial optimization problems
• Complexity of uniqueness and local search in quadratic 0-1 programming
• Extremal values of global tolerances in combinatorial optimization with an additive objective function
• F-modular spaces
• Global tolerances in the problems of combinatorial optimization with an additive objective function
• Orlicz spaces and modular spaces
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Sensitivity analysis of list scheduling heuristics
• Some concepts of stability analysis in combinatorial optimization
• The Tolerance Approach to Sensitivity Analysis of Matrix Coefficients in Linear Programming
• Tolerance-based branch and bound algorithms for the ATSP

Cited In (2)

• Note on a vertex stability radius in the shortest path problem
• Stability analysis of some discrete optimization algorithms

This page was built for publication: Stability analysis in discrete optimization involving generalized addition operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896189)