Interval linear programming provides a mathematical tool for modeling practical optimization problems affected by uncertainty. One of the essential tasks in optimization with interval-valued data is determining the range of optimal values of the objective function, i.e. finding the best and the worst possible optimal value. For general interval linear programs, this leads to an NP-hard problem. Therefore, methods for computing a quick and sufficiently tight approximation of these extremal optimal values are also desired. In this talk, we discuss the (in)approximability properties of this problem and propose a method for obtaining an approximation of the optimal value range. We also address some special classes of interval linear programs, for which the optimal value range can be computed exactly in polynomial time and study how the complexity of the problem varies with respect to the number and structure of interval coefficients in the given program.