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.