Calculation of exact bounds for the solution set of linear interval systems (Q5961705)

An algorithm for calculating the exact bounds for each component of the solution set of a linear interval system is described. This problem is known to be NP-hard. The proposed algorithm gives an error message if the solution is unbounded. The computations are done in \(p\) calls of a polynomial time algorithm, where \(p\) is the number of orthants intersecting the problem set. It is shown that the NP-hardness of the problem stems form the fact that the solution set may intersect exponentially many orthants.