Complexity of computing the worst optimal value of interval transportation problems

Elif Garajová () and Miroslav Rada ()
Additional contact information
Elif Garajová: Faculty of Mathematics and Physics, Charles University
Miroslav Rada: Faculty of Informatics and Statistics, Prague University of Economics and Business

Central European Journal of Operations Research, 2025, vol. 33, issue 3, No 9, 819-834

Abstract: Abstract 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.

Keywords: Transportation problem; Interval data; Uncertainty; Optimal value (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10100-024-00947-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:33:y:2025:i:3:d:10.1007_s10100-024-00947-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-024-00947-8

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().