The worst case finite optimal value in interval linear programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385569" target="_blank" >RIV/00216208:11320/18:10385569 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.17535/crorr.2018.0019" target="_blank" >https://doi.org/10.17535/crorr.2018.0019</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.17535/crorr.2018.0019" target="_blank" >10.17535/crorr.2018.0019</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The worst case finite optimal value in interval linear programming

Popis výsledku v původním jazyce

We consider a linear programming problem, in which possibly all coefficients are subject to uncertainty in the form of deterministic intervals. The problem of computing the worst case optimal value has already been thoroughly investigated in the past. Notice that it might happen that the value can be infinite due to infeasibility of some instances. This is a serious drawback if we know a priori that all instances should be feasible. Therefore we focus on the feasible instances only and study the problem of computing the worst case finite optimal value. We present a characterization for the general case and investigate special cases, too. We show that the problem is easy to solve provided interval uncertainty affects the objective function only, but the problem becomes intractable in case of intervals in the right-hand side of the constraints. We also propose a finite reduction based on inspecting candidate bases. We show that processing a given basis is still an NP-hard problem even with non-interval constraint matrix, however, the problem becomes tractable as long as uncertain coefficients are situated either in the objective function or in the right-hand side only.

Název v anglickém jazyce

The worst case finite optimal value in interval linear programming

Popis výsledku anglicky

We consider a linear programming problem, in which possibly all coefficients are subject to uncertainty in the form of deterministic intervals. The problem of computing the worst case optimal value has already been thoroughly investigated in the past. Notice that it might happen that the value can be infinite due to infeasibility of some instances. This is a serious drawback if we know a priori that all instances should be feasible. Therefore we focus on the feasible instances only and study the problem of computing the worst case finite optimal value. We present a characterization for the general case and investigate special cases, too. We show that the problem is easy to solve provided interval uncertainty affects the objective function only, but the problem becomes intractable in case of intervals in the right-hand side of the constraints. We also propose a finite reduction based on inspecting candidate bases. We show that processing a given basis is still an NP-hard problem even with non-interval constraint matrix, however, the problem becomes tractable as long as uncertain coefficients are situated either in the objective function or in the right-hand side only.

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í

2018

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

Croatian Operational Research Review [online]

ISSN

1848-9931

e-ISSN

—

Svazek periodika

9

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

HR - Chorvatská republika

Počet stran výsledku

10

Strana od-do

245-254

Kód UT WoS článku

000453297700009

EID výsledku v databázi Scopus

2-s2.0-85058806012