Milan Hladík. A general approach to handle complex sensitivity analysis in linear programming. In Proceedings of the 17th International Symposium on Operational Research SOR'23, Bled, Slovenia, September 20-22, 2023, pp. 397–400, Slovenian Society INFORMATIKA, Ljubljana, Slovenia, 2023.
The sensitivity analysis in linear programming is a well-known standard, technique to deal with variations of selected entries. Its limitation is that is focuses only on sensitivity of one coefficient or other simple cases. The real life is, however, more complicated. To handle a bit more complex data variations, various approaches were introduced and studied. Herein, we address variations of possibly all input data, controlled by a certain matrix norm. More concretely, the aim is to compute the maximum variation of the data in the norm such that the computed optimal basis remains optimal. First, we present results valid for a general matrix norm. Then we inspect particular norms, such as the spectral and the maximum norm. We also analyse computational complexity to know for which norms the problem is efficiently computable and for which it is NP-hard.
@inProceedings{Hla2023d,
author = "Milan Hlad\'{\i}k",
title = "A general approach to handle complex sensitivity analysis in linear programming",
editor = "S. Drobne and others",
feditor = "S. Drobne and L. Zadnik Stirn and M. Kljajić Borštnar and J. Povh and J. Žerovnik",
booktitle = "Proceedings of the 17th International Symposium on Operational Research SOR'23, Bled, Slovenia, September 20-22, 2023",
publisher = "Slovenian Society INFORMATIKA",
address = "Ljubljana, Slovenia",
pages = "397-400",
year = "2023",
isbn = "978-961-6165-61-7",
url = "https://www.drustvo-informatika.si/sekcije-drustva?stran=publikacije-sor",
bib2html_dl_pdf = "https://drustvo-informatika.si/uploads/documents/6a1c2595-7d3f-4dd2-ab6c-9ed9b168c19d//SOR23Proceedings.pdf",
abstract = "The sensitivity analysis in linear programming is a well-known standard, technique to deal with variations of selected entries. Its limitation is that is focuses only on sensitivity of one coefficient or other simple cases. The real life is, however, more complicated. To handle a bit more complex data variations, various approaches were introduced and studied. Herein, we address variations of possibly all input data, controlled by a certain matrix norm. More concretely, the aim is to compute the maximum variation of the data in the norm such that the computed optimal basis remains optimal. First, we present results valid for a general matrix norm. Then we inspect particular norms, such as the spectral and the maximum norm. We also analyse computational complexity to know for which norms the problem is efficiently computable and for which it is NP-hard.",
keywords = "Linear programming; Sensitivity analysis; Tolerance analysis; Matrix norm, NP-hardness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44