Integer Programming Reformulations in Interval Linear Programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437050" target="_blank" >RIV/00216208:11320/21:10437050 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-86841-3_1" target="_blank" >https://doi.org/10.1007/978-3-030-86841-3_1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-86841-3_1" target="_blank" >10.1007/978-3-030-86841-3_1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Integer Programming Reformulations in Interval Linear Programming

Popis výsledku v původním jazyce

Interval linear programming provides a mathematical model for optimization problems affected by uncertainty, in which the uncertain data can be independently perturbed within the given lower and upper bounds. Many tasks in interval linear programming, such as describing the feasible set or computing the range of optimal values, can be solved by the orthant decomposition method, which reduces the interval problem to a set of linear-programming subproblems-one linear program over each orthant of the solution space. In this paper, we explore the possibility of utilizing the existing integer programming techniques in tackling some of these difficult problems by deriving a mixed-integer linear programming reformulation. Namely, we focus on the optimal value range problem, which is NP-hard for general interval linear programs. For this problem, we compare the obtained reformulation with the traditionally used orthant decomposition and also with the non-linear absolute-value formulation that serves as a basis for both of the former approaches. (C) 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Název v anglickém jazyce

Integer Programming Reformulations in Interval Linear Programming

Popis výsledku anglicky

Interval linear programming provides a mathematical model for optimization problems affected by uncertainty, in which the uncertain data can be independently perturbed within the given lower and upper bounds. Many tasks in interval linear programming, such as describing the feasible set or computing the range of optimal values, can be solved by the orthant decomposition method, which reduces the interval problem to a set of linear-programming subproblems-one linear program over each orthant of the solution space. In this paper, we explore the possibility of utilizing the existing integer programming techniques in tackling some of these difficult problems by deriving a mixed-integer linear programming reformulation. Namely, we focus on the optimal value range problem, which is NP-hard for general interval linear programs. For this problem, we compare the obtained reformulation with the traditionally used orthant decomposition and also with the non-linear absolute-value formulation that serves as a basis for both of the former approaches. (C) 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Druh

C - Kapitola v odborné knize

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í

2021

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-030-86841-3

Počet stran výsledku

11

Strana od-do

3-13

Počet stran knihy

247

Název nakladatele

Springer Nature

Místo vydání

Cham

Kód UT WoS kapitoly

—