Checking weak optimality and strong boundedness in interval linear programming
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Checking weak optimality and strong boundedness in interval linear programming
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Checking weak optimality and strong boundedness in interval linear programming
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
50201 - Economic Theory
Návaznosti výsledku
Projekt
<a href="/cs/project/GA18-04735S" target="_blank" >GA18-04735S: Nové přístupy pro relaxační a aproximační techniky v deterministické globální optimalizaci</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2019
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Soft Computing
ISSN
1432-7643
e-ISSN
—
Svazek periodika
23
Číslo periodika v rámci svazku
9
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
9
Strana od-do
2937-2945
Kód UT WoS článku
000465459700009
EID výsledku v databázi Scopus
2-s2.0-85053505477