Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Checking weak optimality and strong boundedness in interval linear programming

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

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

  • Výsledek na webu

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

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/s00500-018-3520-3" target="_blank" >10.1007/s00500-018-3520-3</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Checking weak optimality and strong boundedness in interval linear programming

  • Popis výsledku v původním jazyce

    Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.

  • Název v anglickém jazyce

    Checking weak optimality and strong boundedness in interval linear programming

  • Popis výsledku anglicky

    Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    50201 - Economic Theory

Návaznosti výsledku

  • 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)

Ostatní

  • 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ů

Údaje specifické pro druh výsledku

  • Název periodika

    Soft Computing

  • ISSN

    1432-7643

  • e-ISSN

  • Svazek periodika

    23

  • Číslo periodika v rámci svazku

    9

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    9

  • Strana od-do

    2937-2945

  • Kód UT WoS článku

    000465459700009

  • EID výsledku v databázi Scopus

    2-s2.0-85053505477