One of the basic tools to describe uncertainty in a linear programming model is interval linear programming, where parameters are assumed to vary within a priori known intervals. One of the main topics addressed in this context is determining the optimal value range, that is, the best and the worst of all the optimal values of the objective function among all the realizations of the uncertain parameters. For the equality constraint problems, computing the best optimal value is an easy task, but the worst optimal value calculation is known to be NP-hard. In this study, we propose new methods to determine bounds for the worst optimal value, and we evaluate them on a set of randomly generated instances.
Bounds on the worst optimal value in interval linear programming
Gentili M.
2019-01-01
Abstract
One of the basic tools to describe uncertainty in a linear programming model is interval linear programming, where parameters are assumed to vary within a priori known intervals. One of the main topics addressed in this context is determining the optimal value range, that is, the best and the worst of all the optimal values of the objective function among all the realizations of the uncertain parameters. For the equality constraint problems, computing the best optimal value is an easy task, but the worst optimal value calculation is known to be NP-hard. In this study, we propose new methods to determine bounds for the worst optimal value, and we evaluate them on a set of randomly generated instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
