Some concepts of stability analysis in combinatorial optimization

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

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

Publication date: 17 May 1995

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

zbMATH Keywords

stability analysis for discrete optimization; stability ball of optimal or approximate solutions

Mathematics Subject Classification ID

05C05: Trees

90C31: Sensitivity, stability, parametric optimization

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

05C38: Paths and cycles

90B80: Discrete location and assignment

Related Items

A general approach to studying the stability of a Pareto optimal solution of a vector integer linear programming problem, On the Hardness of Reoptimization, Analyse de sensibilité pour les problèmes linéaires en variables 0-1, An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual, On combinatorial optimization problems on matroids with uncertain weights, Stability aspects of the traveling salesman problem based on \(k\)-best solutions, On the quasistability of trajectory problems of vector optimization, On the complexity of postoptimality analysis of \(0/1\) programs, Calculation of stability radii for combinatorial optimization problems, Stability of a schedule minimizing mean flow time, Optimal makespan scheduling with given bounds of processing times, Boolean problem of sequential minimization of moduli of linear functions and stability theorems, Stability radius of a lexicographic optimum of a vector problem of Boolean programming, Sensitivity analysis in the single-machine scheduling problem with max-min criterion, Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem, Reoptimization of the Metric Deadline TSP

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