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)

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.

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

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

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)

Cites Work

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

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)