Linear programming sensitivity measured by the optimal value worst-case analysis
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10491182" target="_blank" >RIV/00216208:11320/24:10491182 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=PYjzQYCtX9" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=PYjzQYCtX9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1080/10556788.2024.2329590" target="_blank" >10.1080/10556788.2024.2329590</a>
Alternative languages
Result language
angličtina
Original language name
Linear programming sensitivity measured by the optimal value worst-case analysis
Original language description
This paper introduces the concept of a derivative of the optimal value function in linear programming (LP). Basically, it is the worst case optimal value of an interval LP problem when the nominal data are inflated to intervals according to given perturbation patterns. By definition, the derivative expresses how the optimal value can worsen when the data are subject to variations. In addition, it also gives a certain sensitivity measure or condition number of an LP problem. If the LP problem is nondegenerate, the derivatives are easy to calculate from the computed primal and dual optimal solutions. For degenerate problems, the computation is more difficult. We propose an upper bound and some kind of characterization, but there are many open problems remaining. We carried out numerical experiments with specific LP problems and with real LP data from Netlib repository. They show that the derivatives give a suitable sensitivity measure of LP problems. It remains an open problem how to efficiently and rigorously handle degenerate problems.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
50201 - Economic Theory
Result continuities
Project
<a href="/en/project/GA22-11117S" target="_blank" >GA22-11117S: Global sensitivity analysis and stability in optimization problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Optimization Methods and Software
ISSN
1055-6788
e-ISSN
1029-4937
Volume of the periodical
39
Issue of the periodical within the volume
5
Country of publishing house
GB - UNITED KINGDOM
Number of pages
17
Pages from-to
1168-1184
UT code for WoS article
001198411200001
EID of the result in the Scopus database
2-s2.0-85190255204