On the optimal solution set 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%3A10397331" target="_blank" >RIV/00216208:11320/19:10397331 - isvavai.cz</a>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On the optimal solution set in interval linear programming
Original language description
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.
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
Computational Optimization and Applications
ISSN
0926-6003
e-ISSN
—
Volume of the periodical
72
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
24
Pages from-to
269-292
UT code for WoS article
000456934700009
EID of the result in the Scopus database
2-s2.0-85052533854