Checking weak optimality and strong boundedness in interval linear programming
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10397333" target="_blank" >RIV/00216208:11320/19:10397333 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1VmXhFqDy-" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1VmXhFqDy-</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00500-018-3520-3" target="_blank" >10.1007/s00500-018-3520-3</a>
Alternative languages
Result language
angličtina
Original language name
Checking weak optimality and strong boundedness in interval linear programming
Original language description
Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.
Czech name
—
Czech description
—
Classification
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
Result continuities
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)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Soft Computing
ISSN
1432-7643
e-ISSN
—
Volume of the periodical
23
Issue of the periodical within the volume
9
Country of publishing house
US - UNITED STATES
Number of pages
9
Pages from-to
2937-2945
UT code for WoS article
000465459700009
EID of the result in the Scopus database
2-s2.0-85053505477