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. (C) 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.