Robust sensitivity analysis of the optimal value of linear programming

DOI10.1080/10556788.2016.1256400MaRDI QIDQ4594851zbMATH OpenOpenAlexFDO

Authors Guanglin Xu, Samuel Burer

Publication date 24 November 2017

Published in Optimization Methods \& Software (Search for Journal in Brave)

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

zbMATH Keywords

copositive programmingminimax problemnon-convex quadratic programmingsemidefinite programmingsensitivity analysisuncertainty set

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Minimax problems in mathematical programming (90C47)

Abstract: We propose a framework for sensitivity analysis of linear programs (LPs) in minimization form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties to worst-case linear optimization and two-stage adaptive optimization. We define the minimum (best-case) and maximum (worst-case) LP optimal values, p- and p+, over the uncertainty set, and we discuss issues of finiteness, attainability, and computational complexity. While p- and p+ are difficult to compute in general, we prove that they equal the optimal values of two separate, but related, copositive programs. We then develop tight, tractable conic relaxations to provide lower and upper bounds on p- and p+, respectively. We also develop techniques to assess the quality of the bounds, and we validate our approach computationally on several examples from--and inspired by--the literature. We find that the bounds on p- and p+ are very strong in practice and, in particular, are at least as strong as known results for specific cases from the literature.

Recommendations

• Robust sensitivity analysis for linear programming with ellipsoidal perturbation
• Sensitivity analysis in linear programming: Just be careful!
• Using bounds on the data in linear programming: The tolerance approach to sensitivity analysis
• Stability and sensitivity of uncertain linear programs
• POSITIVE SENSITIVITY ANALYSIS IN LINEAR PROGRAMMING

Cited in

(13)

• A global tolerance approach to sensitivity analysis in linear programming
• An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation
• Robust sensitivity analysis for linear programming with ellipsoidal perturbation
• Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality
• Strictly sensitivity analysis for linear programming problems with upper bounds
• A parallel computational model for sensitivity analysis in optimization for robustness
• scientific article; zbMATH DE number 3982919 (Why is no real title available?)
• Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization
• scientific article; zbMATH DE number 883863 (Why is no real title available?)
• Multiple cost coefficients sensitivity theorems of integer linear optimization
• Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach
• Measures of global sensitivity in linear programming: applications in banking sector
• Linear programming sensitivity measured by the optimal value worst-case analysis

This page was built for publication: Robust sensitivity analysis of the optimal value of linear programming

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