On computation methods of the minimax regret solution for linear programming problems with uncertain objective function coefficients

We investigate the computation methods for minimax regret solutions to linear programming problems with uncertain objective function coefficients. The previously proposed solution algorithms, two phase approach, bilevel programming approach and branch and bound approach are reviewed. An outer approximation approach is proposed. By numerical experiments, the efficiency of the solution algorithms is compared. It is shown that a computation method based on the branch and bound approach is fastest in the interval coefficient case and that the outer approximation approach is effective as the problem size increases and can be fastest in the polytope case among the three approaches