Stability of the optimal basis of a linear program under uncertainty

DOI10.1016/0167-6377(93)90077-TMaRDI QIDQ2367033zbMATH OpenOpenAlexFDO

Authors Jiří Rohn

Publication date 16 August 1993

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(93)90077-t

zbMATH Keywords

optimal basisstabilityvariations within intervals

Mathematics Subject Classification ID

Linear programming (90C05) Sensitivity, stability, parametric optimization (90C31)

Review text

The article deals with a family of linear programming problems with all the data varying independently of each other within some prescribed tolerances. The stability of the optimal solution of such problems is studied. If \(B\) means an optimal basis then the \(B\)-stable and strongly \(B\)-stable problems are defined. The main result consists in a proof that the optimal basis \(B\) of a linear programming problem remains optimal under variations of all data within prescribed tolerances if and only if a finite subset of explicitly given linear programming problems have the same property. Unfortunately, the cardinality of this subset is exponential in the number of constraints.

Recommendations

• Stability and sensitivity of uncertain linear programs
• scientific article; zbMATH DE number 4072718
• Stability of the linear complementarity problem properties under interval uncertainty
• scientific article; zbMATH DE number 3906245
• scientific article; zbMATH DE number 29658
• Stability for linearly constrained optimization problems
• scientific article; zbMATH DE number 3920198
• scientific article; zbMATH DE number 2219543
• On the stability of the feasible set in linear optimization
• An approach to linear programming under uncertainty

Cites work

• An existence theorem for systems of linear equations
• scientific article; zbMATH DE number 3523317 (Why is no real title available?)
• scientific article; zbMATH DE number 3634009 (Why is no real title available?)
• scientific article; zbMATH DE number 3446685 (Why is no real title available?)
• Sensitivitätsanalysen und parametrische Programmierung
• Strong solvability of interval linear programming problems
• Systems of linear interval equations

Cited in

(14)

• Bounds on mean absolute deviation portfolios under interval-valued expected future asset returns
• Stability of the linear complementarity problem properties under interval uncertainty
• Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomially-solvable cases
• Monte Carlo simulation for computing the worst value of the objective function in the interval linear programming
• How to determine basis stability in interval linear programming
• Sufficient condition of basis stability of an interval linear programming problem
• Duality for inexact linear programming problems^∗
• scientific article; zbMATH DE number 4145658 (Why is no real title available?)
• scientific article; zbMATH DE number 3978819 (Why is no real title available?)
• scientific article; zbMATH DE number 562322 (Why is no real title available?)
• An improved three-step method for solving the interval linear programming problems
• The worst case finite optimal value in interval linear programming
• A novel interval linear programming based on probabilistic dominance
• Quantifying outcome functions of linear programs: an approach based on interval-valued right-hand sides

This page was built for publication: Stability of the optimal basis of a linear program under uncertainty

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