Maximum excess dominance: Identifying impractical solutions in linear problems with interval coefficients

In this paper, we propose the concept of maximum excess dominance (MED) and illustrate how it can be used to compare solutions in linear optimization problems with interval objective coefficients. When a solution dominates another solution with MED, the expected outcome of the former is guaranteed to be better than that of the latter across a wide range of probability distributions. Hence, MED can be used to eliminate dominated solutions from consideration. Furthermore, we provide an efficient way to check if a solution is dominated by another feasible solution in binary optimization problems and illustrate how dominated solutions can be pruned away by introducing MED constraints to the original binary optimization formulation. We also propose an algorithm to find the best non-dominated solution and conduct computational experiments to evaluate its performance.