Integer Programming Reformulations in Interval Linear Programming
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Integer Programming Reformulations in Interval Linear Programming
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
C - Chapter in a specialist book
CEP classification
—
OECD FORD branch
50201 - Economic Theory
Result continuities
Project
<a href="/en/project/GA18-04735S" target="_blank" >GA18-04735S: Novel approaches for relaxation and approximation techniques in deterministic global optimization</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Book/collection name
AIRO Springer Series
ISBN
978-3-030-86841-3
Number of pages of the result
11
Pages from-to
3-13
Number of pages of the book
247
Publisher name
Springer Nature
Place of publication
Cham
UT code for WoS chapter
—