Complexity Issues in Interval Linear Programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10472191" target="_blank" >RIV/00216208:11320/23:10472191 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-28863-0_11" target="_blank" >https://doi.org/10.1007/978-3-031-28863-0_11</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-28863-0_11" target="_blank" >10.1007/978-3-031-28863-0_11</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity Issues in Interval Linear Programming

Popis výsledku v původním jazyce

Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible values the coefficients may attain, independently of each other. They usually originate from a certain uncertainty of obtaining the data, but they can also be used in a type of a sensitivity analysis. The goal of interval linear programming is to provide tools for analysing the effects of data variations on the optimal value, optimal solutions and other characteristics. This paper is a contribution to computational complexity theory. Some problems in interval linear programming are known to be polynomially solvable, but some were proved to be NP-hard. We help to improve this classification by stating several novel complexity results. In particular, we show NP-hardness of the following problems: checking whether a particular value is attained as an optimal value; testing connectedness and convexity of the optimal solution set; and checking whether a given solution is robustly optimal for each realization of the interval values.

Název v anglickém jazyce

Complexity Issues in Interval Linear Programming

Popis výsledku anglicky

Interval linear programming studies linear programming problems with interval coefficients. Herein, the intervals represent a range of possible values the coefficients may attain, independently of each other. They usually originate from a certain uncertainty of obtaining the data, but they can also be used in a type of a sensitivity analysis. The goal of interval linear programming is to provide tools for analysing the effects of data variations on the optimal value, optimal solutions and other characteristics. This paper is a contribution to computational complexity theory. Some problems in interval linear programming are known to be polynomially solvable, but some were proved to be NP-hard. We help to improve this classification by stating several novel complexity results. In particular, we show NP-hardness of the following problems: checking whether a particular value is attained as an optimal value; testing connectedness and convexity of the optimal solution set; and checking whether a given solution is robustly optimal for each realization of the interval values.

Druh

C - Kapitola v odborné knize

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-11117S" target="_blank" >GA22-11117S: Globální analýza citlivosti a stabilita v optimalizačních úlohách</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

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 knihy nebo sborníku

AIRO Springer Series

ISBN

978-3-031-28862-3

Počet stran výsledku

11

Strana od-do

123-133

Počet stran knihy

366

Název nakladatele

Springer

Místo vydání

Cham

Kód UT WoS kapitoly

—