Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125736" target="_blank" >RIV/00216208:11320/12:10125736 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s11590-011-0315-1" target="_blank" >http://dx.doi.org/10.1007/s11590-011-0315-1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11590-011-0315-1" target="_blank" >10.1007/s11590-011-0315-1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

Popis výsledku v původním jazyce

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient ifit is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.

Název v anglickém jazyce

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

Popis výsledku anglicky

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient ifit is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

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

Optimization Letters

ISSN

1862-4472

e-ISSN

—

Svazek periodika

6

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

7

Strana od-do

893-899

Kód UT WoS článku

000304624700007

EID výsledku v databázi Scopus

—