The worst case finite optimal value in interval linear programming

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385569" target="_blank" >RIV/00216208:11320/18:10385569 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.17535/crorr.2018.0019" target="_blank" >https://doi.org/10.17535/crorr.2018.0019</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.17535/crorr.2018.0019" target="_blank" >10.17535/crorr.2018.0019</a>

Result language
angličtina
Original language name
The worst case finite optimal value in interval linear programming
Original language description
We consider a linear programming problem, in which possibly all coefficients are subject to uncertainty in the form of deterministic intervals. The problem of computing the worst case optimal value has already been thoroughly investigated in the past. Notice that it might happen that the value can be infinite due to infeasibility of some instances. This is a serious drawback if we know a priori that all instances should be feasible. Therefore we focus on the feasible instances only and study the problem of computing the worst case finite optimal value. We present a characterization for the general case and investigate special cases, too. We show that the problem is easy to solve provided interval uncertainty affects the objective function only, but the problem becomes intractable in case of intervals in the right-hand side of the constraints. We also propose a finite reduction based on inspecting candidate bases. We show that processing a given basis is still an NP-hard problem even with non-interval constraint matrix, however, the problem becomes tractable as long as uncertain coefficients are situated either in the objective function or in the right-hand side only.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
50201 - Economic Theory

Project
<a href="/en/project/GA18-04735S" target="_blank" >GA18-04735S: Novel approaches for relaxation and approximation techniques in deterministic global optimization</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)