Strong Unboundedness of Interval Linear Programming Problems

A linear programming problem whose coefficients are prescribed by intervals is called strongly unbounded if each linear programming problem obtained by fixing coefficients in these intervals is unbounded. In the main result of this paper a necessary and sufficient condition for strong unboundedness of an interval linear programming problem is described. In order to have a full picture we also show conditions for strong feasibility and strong solvability of this problem. The necessary and sufficient conditions for strong feasibility, strong solvability and strong unboundedness can be verified by checking the appropriate properties by the finite algorithms. Checking strong feasibility and checking strong solvability are NP-hard. We show that checking strong unboundedness is NP-hard as well.