On the optimal solution set in interval linear programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10397331" target="_blank" >RIV/00216208:11320/19:10397331 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=ZcPJKUZfKM" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=ZcPJKUZfKM</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10589-018-0029-8" target="_blank" >10.1007/s10589-018-0029-8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the optimal solution set in interval linear programming

Popis výsledku v původním jazyce

Determining the set of all optimal solutions of a linear program with interval data is one of the most challenging problems discussed in interval optimization. In this paper, we study the topological and geometric properties of the optimal set and examine sufficient conditions for its closedness, boundedness, connectedness and convexity. We also prove that testing boundedness is co-NP-hard for inequality-constrained problems with free variables. Furthermore, we prove that computing the exact interval hull of the optimal set is NP-hard for linear programs with an interval right-hand-side vector. We then propose a new decomposition method for approximating the optimal solution set based on complementary slackness and show that the method provides the exact description of the optimal set for problems with afixed coefficient matrix. Finally, we conduct computational experiments to compare our method with the existing orthant decomposition method.

Název v anglickém jazyce

On the optimal solution set in interval linear programming

Popis výsledku anglicky

Determining the set of all optimal solutions of a linear program with interval data is one of the most challenging problems discussed in interval optimization. In this paper, we study the topological and geometric properties of the optimal set and examine sufficient conditions for its closedness, boundedness, connectedness and convexity. We also prove that testing boundedness is co-NP-hard for inequality-constrained problems with free variables. Furthermore, we prove that computing the exact interval hull of the optimal set is NP-hard for linear programs with an interval right-hand-side vector. We then propose a new decomposition method for approximating the optimal solution set based on complementary slackness and show that the method provides the exact description of the optimal set for problems with afixed coefficient matrix. Finally, we conduct computational experiments to compare our method with the existing orthant decomposition method.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

50201 - Economic Theory

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)

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ů

Název periodika

Computational Optimization and Applications

ISSN

0926-6003

e-ISSN

—

Svazek periodika

72

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

24

Strana od-do

269-292

Kód UT WoS článku

000456934700009

EID výsledku v databázi Scopus

2-s2.0-85052533854