Linear programming sensitivity measured by the optimal value worst-case analysis

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Linear programming sensitivity measured by the optimal value worst-case analysis

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Linear programming sensitivity measured by the optimal value worst-case analysis

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

50201 - Economic Theory

Projekt

<a href="/cs/project/GA22-11117S" target="_blank" >GA22-11117S: Globální analýza citlivosti a stabilita v optimalizačních úlohách</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Optimization Methods and Software

ISSN

1055-6788

e-ISSN

1029-4937

Svazek periodika

39

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

17

Strana od-do

1168-1184

Kód UT WoS článku

001198411200001

EID výsledku v databázi Scopus

2-s2.0-85190255204