Complexity of computing the worst optimal value of interval transportation problems

Interval linear programming provides a mathematical model for transportation problems, in which the values of supply, demand and the transportation costs are affected by uncertainty and can be independently perturbed within the given lower and upper bounds. For this model, we analyze the computational complexity of the problem of finding the worst (finite) optimal value over all possible choices of the uncertain data. First, we show that a recent result from bilevel programming implies NP-hardness of computing the worst optimal value for the equation-constrained formulation, in which the supplies have to be depleted and the demands have to be met exactly. Building on the result, we prove that computing the value exactly is NP-hard for all commonly used formulations of the interval transportation problem. Namely, we prove that a direct transformation of the equation constraints into inequalities preserves the worst finite optimal value of a weakly feasible interval transportation problem. We also highlight two promising classes not covered by the presented NP-hardness proof, for which no polynomial-time algorithm for computing the worst optimal value is known and whose complexity is still open: problems immune against the more-for-less paradox and problems with a Monge cost matrix.