An enumerative algorithm for computing all possibly optimal solutions to an interval LP

Interval programming techniques are a valuable approach for tackling uncertainty in mathematical programming models, because they only require the knowledge of the feasible range of variation of the model coefficients. Nevertheless, the use of these techniques has some limitations, namely when the number of decision variables with interval coefficients is high since the number of objective functions at stake in the sub-problem for testing the (weak) efficiency of each non-basic variable may be easily out of an acceptable computational effort. A similar problem may arise with the number of sub-problems for testing the multi-parametric optimality of each solution obtained (that is, to check whether the solution is possibly optimal or not) and the multi-parametric optimality of each edge by using the all emanating edges algorithm. An alternative algorithm is suggested that allows obtaining all possibly optimal solutions, which fulfill the formal criteria of optimality in a feasible bounded region. Copyright Sociedad de Estadística e Investigación Operativa 2014