A new mixed integer formulation for the maximum regret problem

The minimax 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 presents a new formulation for the latter problem that exploits the piecewise linear structure of the cost coefficients. Computational results indicate that this yields a stronger formulation than the previous approach.