Journal article
Robust sensitivity analysis of the optimal value of linear programming
Optimization methods & software, Vol.32(6), pp.1187-1205
11/02/2017
DOI: 10.1080/10556788.2016.1256400
Abstract
We propose a framework for sensitivity analysis (SA) of linear programs (LPs) in minimization form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modelled in a compact, convex, and tractable uncertainty set. This framework unifies and extends multiple approaches for LP SA 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,
and
, over the uncertainty set, and we discuss issues of finiteness, attainment, and computational complexity. While
and
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
and
, 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
and
are very strong in practice and, in particular, are at least as strong as known results for specific cases from the literature.
Details
- Title: Subtitle
- Robust sensitivity analysis of the optimal value of linear programming
- Creators
- Guanglin Xu - University of IowaSamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Optimization methods & software, Vol.32(6), pp.1187-1205
- Publisher
- Taylor & Francis
- DOI
- 10.1080/10556788.2016.1256400
- ISSN
- 1055-6788
- eISSN
- 1029-4937
- Grant note
- AFRL Mathematical Modeling and Optimization Institute Singapore University of Technology and Design (10.13039/501100007040) National University of Singapore (10.13039/501100001352)
- Language
- English
- Date published
- 11/02/2017
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380439102771
Metrics
5 Record Views