Milan Hladík. Complexity issues in interval linear programming. In P. Cappanera et al., editor, Optimization and Decision Science: Operations Research, Inclusion and Equity, AIRO Springer Series, pp. 123–133, Springer, Cham, 2023.
[PDF] [gzipped postscript] [postscript] [HTML]
Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible values the coefficients may attain, independently of each other. They usually originate from a certain uncertainty of obtaining the data, but they can also be used in a type of a sensitivity analysis. The goal of interval linear programming is to provide tools for analysing the effects of data variations on the optimal value, optimal solutions and other characteristics. This paper is a contribution to computational complexity theory. Some problems in interval linear programming are known to be polynomially solvable, but some were proved to be NP-hard. We help to improve this classification by stating several novel complexity results. In particular, we show NP-hardness of the following problems: checking whether a particular value is attained as an optimal value; testing connectedness and convexity of the optimal solution set; and checking whether a given solution is robustly optimal for each realization of the interval values.
@inCollection{Hla2023c,
author = "Milan Hlad\'{\i}k",
title = "Complexity issues in interval linear programming",
editor = "Cappanera et al., P.",
feditor = " Paola Cappanera and Matteo Lapucci and Fabio Schoen and Marco Sciandrone and Fabio Tardella and Filippo Visintin",
booktitle = "Optimization and Decision Science: Operations Research, Inclusion and Equity",
fbooktitle = "Optimization and Decision Science: Operations Research, Inclusion and Equity. ODS, Florence, Italy, August 30-September 2, 2022",
publisher = "Springer",
address = "Cham",
sseries = "AIROSS",
series = "AIRO Springer Series",
volume = "9",
pages = "123-133",
year = "2023",
doi = "10.1007/978-3-031-28863-0_11",
isbn = "978-3-031-28862-3",
issn = "2523-7047",
url = "https://link.springer.com/chapter/10.1007/978-3-031-28863-0_11",
bib2html_dl_html = "https://doi.org/10.1007/978-3-031-28863-0_11",
abstract = "Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible values the coefficients may attain, independently of each other. They usually originate from a certain uncertainty of obtaining the data, but they can also be used in a type of a sensitivity analysis. The goal of interval linear programming is to provide tools for analysing the effects of data variations on the optimal value, optimal solutions and other characteristics. This paper is a contribution to computational complexity theory. Some problems in interval linear programming are known to be polynomially solvable, but some were proved to be NP-hard. We help to improve this classification by stating several novel complexity results. In particular, we show NP-hardness of the following problems: checking whether a particular value is attained as an optimal value; testing connectedness and convexity of the optimal solution set; and checking whether a given solution is robustly optimal for each realization of the interval values.",
keywords = "Interval linear programming; NP-hardness; Computational complexity; Connectedness; Robust optimality",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42