H. Mausser and M. Laguna
Journal of the Operational Research Society, vol. 50, pp. 1063-1070 (1999)
The minimax relative regret solution to a linear program with interval objective function coefficients can be found using an algorithm that, at each iteration, solves a linear program to generate a candidate solution and a mixed integer program to find the corresponding maximum regret. This paper first shows that there exists a regret-maximizing solution in which all uncertain costs are at a bound, and then uses this fact to derive a mixed integer programming (MIP) formulation for the latter problem. Computational experiments demonstrate that this approach is effective for problems with up to 50 uncertain costs, significantly improving upon the existing enumerative method.
