Elif Garajová, Miroslav Rada, and Milan Hladík. Integer programming reformulations in interval linear programming. In R. Cerulli and others, editors, Optimization and Decision Science, AIRO Springer Series, pp. 3–13, Springer, Cham, 2021.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@inCollection{GarRad2021b,
author = "Elif Garajov\'{a} and Miroslav Rada and Milan Hlad\'{\i}k",
title = "Integer programming reformulations in interval linear programming",
editor = "R. Cerulli and others",
feditor = "Raffaele Cerulli and Mauro Dell'Amico and Francesca Guerriero and Dario Pacciarelli and Antonio Sforza",
booktitle = "Optimization and Decision Science",
fbooktitle = "Optimization and Decision Science. ODS, Virtual Conference, November 19, 2020",
publisher = "Springer",
address = "Cham",
series = "AIRO Springer Series",
volume = "7",
pages = "3-13",
year = "2021",
doi = "10.1007/978-3-030-86841-3_1",
isbn = "978-3-030-86841-3",
issn = "2523-7047",
url = "https://link.springer.com/chapter/10.1007/978-3-030-86841-3_1",
bib2html_dl_html = "https://doi.org/10.1007/978-3-030-86841-3_1",
abstract = "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.",
keywords = "Interval linear programming; Integer programming; Optimal value range",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44