Two approaches to inner estimations of the optimal solution set in interval linear programming

Abstract

We consider a linear programming problem with uncertain input coefficients. The only information we have are lower and upper bounds for the uncertain values.

This gives rise to the so called interval linear programming. The challenging problem here is to characterize and determine the set of all possible optimal solutions.

Most of the scholars were focus on computing outer bounds for the optimal solution. Herein, we will be interested with computing inner bounds.

We propose a local search algorithm and a genetic algorithm. We compare both methods numerically on random data to ascertain what is their real time complexity and quality of inner estimations.

Keywords

• Interval computation
• Genetic algorithm
• Heuristic
• Linear programming
• Parametric programming