Tolerance analysis in linear systems and linear programming

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10099315" target="_blank" >RIV/00216208:11320/11:10099315 - isvavai.cz</a>

Result on the web

<a href="http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.556635" target="_blank" >http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.556635</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1080/10556788.2011.556635" target="_blank" >10.1080/10556788.2011.556635</a>

Result language

angličtina

Original language name

Tolerance analysis in linear systems and linear programming

Original language description

It is often important to know how different optimality criteria change under input data perturbations. Our aim is to compute tolerances (intervals) for the objective function and the right-hand side coefficients such that these coefficients can independently and simultaneously vary inside their tolerances while preserving the corresponding optimality criterion. We put tolerance analysis in a unified framework that is convenient for algorithmic processing and that is applicable not only in linear programming but for other linear systems as well. We propose an improvement of the known results that is optimal in some sense (the resulting tolerances are maximal and they take into account proportionality). We apply our approach to several optimality invariancies: optimal basis, support set and optimal partition invariancy. Our approach is useful not only for simplex method solvers, but for the interior points methods, too. We show that it is NP-hard to determine the maximal tolerances.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2011

Confidentiality

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

Name of the periodical

Optimization Methods and Software

ISSN

1055-6788

e-ISSN

—

Volume of the periodical

26

Issue of the periodical within the volume

3

Country of publishing house

GB - UNITED KINGDOM

Number of pages

16

Pages from-to

381-396

UT code for WoS article

—

EID of the result in the Scopus database

—