Robust optimal solutions in interval linear programming with forall-exists quantifiers

•Novel kind of robustness in linear programming.•A method to check for robustness of a given point.•Recommendation on how a suitable candidate can be found.•Illustration of applicability in transportation and nutrition problems.

We introduce a novel kind of robustness in linear programming. A solution x* is called robust optimal if for all realizations of the objective function coefficients and the constraint matrix entries from given interval domains there are appropriate choices of the right-hand side entries from their interval domains such that x* remains optimal. We propose a method to check for robustness of a given point, and also recommend how a suitable candidate can be found. We discuss topological properties of the robust optimal solution set, too. We illustrate applicability of our concept in transportation and nutrition problems. Since not every problem has a robust optimal solution, we introduce also a concept of an approximate robust solution and develop an efficient method; as a side effect, we obtain a simple measure of robustness.