Complexity Issues in Interval Linear Programming
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10472191" target="_blank" >RIV/00216208:11320/23:10472191 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-28863-0_11" target="_blank" >https://doi.org/10.1007/978-3-031-28863-0_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-28863-0_11" target="_blank" >10.1007/978-3-031-28863-0_11</a>
Alternative languages
Result language
angličtina
Original language name
Complexity Issues in Interval Linear Programming
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
C - Chapter in a specialist book
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
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
2023
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
Book/collection name
AIRO Springer Series
ISBN
978-3-031-28862-3
Number of pages of the result
11
Pages from-to
123-133
Number of pages of the book
366
Publisher name
Springer
Place of publication
Cham
UT code for WoS chapter
—