Some concepts of stability analysis in combinatorial optimization

DOI10.1016/0166-218X(93)E0126-JzbMath0833.90098OpenAlexW2007898399MaRDI QIDQ1805456

V. K. Leont'ev, Eh. N. Gordeev, Yuri N. Sotskov

Publication date: 17 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0126-j

zbMATH Keywords

stability analysis for discrete optimizationstability ball of optimal or approximate solutions

Mathematics Subject Classification ID

Trees (05C05) Sensitivity, stability, parametric optimization (90C31) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Paths and cycles (05C38) Discrete location and assignment (90B80)

Related Items (44)

Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations ⋮ Postoptimal analysis of the multicriteria combinatorial median location problem ⋮ Approximating the stability region for binary mixed-integer programs ⋮ Stability and accuracy functions in multicriteria linear combinatorial optimization problems ⋮ On stability of a vector combinatorial problem with MINMIN criteria ⋮ Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry ⋮ On combinatorial optimization problems on matroids with uncertain weights ⋮ Stability of a schedule minimizing mean flow time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extending single tolerances to set tolerances ⋮ Optimal makespan scheduling with given bounds of processing times ⋮ Post-optimality approach to prevent cycling in linear MPC target calculation ⋮ Sensitivity analysis for bottleneck assignment problems ⋮ On five types of stability of the lexicographic variant of the combinatorial bottleneck problem ⋮ Stability analysis in discrete optimization involving generalized addition operations ⋮ The multilevel facility location and pricing problems: the computational complexity and the stability analysis ⋮ Unnamed Item ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ Quantitative stability analysis for vector problems of 0-1 programming ⋮ On a measure of quasistability of a certain vector linearly combinatorial Boolean problem ⋮ General approach to estimating the complexity of postoptimality analysis for discrete optimization problems ⋮ Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem ⋮ Postoptimal analysis of a vector minimax combinatorial problem ⋮ Stability radius of a vector investment problem with Savage's minimax risk criteria ⋮ Sensitivity analysis in the single-machine scheduling problem with max-min criterion ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ Boolean problem of sequential minimization of moduli of linear functions and stability theorems ⋮ Reoptimization of the metric deadline TSP ⋮ A general approach to studying the stability of a Pareto optimal solution of a vector integer linear programming problem ⋮ Reoptimization of the Metric Deadline TSP ⋮ On the Hardness of Reoptimization ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Stability aspects of the traveling salesman problem based on \(k\)-best solutions ⋮ On the quasistability of trajectory problems of vector optimization ⋮ Analyse de sensibilité pour les problèmes linéaires en variables 0-1 ⋮ A note on robustness tolerances for combinatorial optimization problems ⋮ On the complexity of postoptimality analysis of \(0/1\) programs ⋮ Investment Boolean problem with savage risk criteria under uncertainty ⋮ Stability radius of a lexicographic optimum of a vector problem of Boolean programming ⋮ Calculation of stability radii for combinatorial optimization problems ⋮ An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual

Cites Work

• A note on two problems in connexion with graphs
• A review of the static, stochastic job sequencing literature
• Stability in bottleneck path problems
• Stability of an optimal schedule
• The stability of the approximate Boolean minimization of a linear form
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Stochastic scheduling problems I — General strategies
• Sensitive and parametric analysis of the maximum flow in a network
• A problem in scheduling theory
• A General Framework for Stochastic One-machine Scheduling Problems with Zero Release Times and No Partial Ordering
• A note on Arc tolerances in sparse shortest-path and network flow problems
• Solution of a parametric integer programming problem
• Computational algorithms for finding the radius of stability in problems of choice
• Parametric trajectory problems
• Stochastic scheduling problems II-set strategies-
• Complexity of some parametric integer and network programming problems
• Independent flows with a discrete-concave expenditure function
• On the Numerical Stability of Simplex-Algorithms
• Steiner problem in networks: A survey
• Algorithms of polynomial complexity for computing the radius of instability in two classes of trajectory problems
• Arc tolerances in shortest path and network flow problems
• Integer programming duality: Price functions and sensitivity analysis
• Sensitivity analysis of optimal matchings
• A shortest augmenting path method for solving minimal perfect matching problems
• The value function of an integer program
• Stability in bottleneck problems
• Postoptimality analysis in integer programming by implicit enumeration: The mixed integer case
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• A Characterization of Stability in Linear Programming
• Optimal schedules with infinitely large stability radius^∗
• Sensitivity Analysis of Multiterminal Flow Networks
• Stability in Nonlinear Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some concepts of stability analysis in combinatorial optimization