Article ID: | iaor20003761 |
Country: | United Kingdom |
Volume: | 50 |
Issue: | 10 |
Start Page Number: | 1063 |
End Page Number: | 1070 |
Publication Date: | Oct 1999 |
Journal: | Journal of the Operational Research Society |
Authors: | Laguna Manuel, Mausser Helmut E. |
Keywords: | programming: integer |
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 (MIP) to find the corresponding maximum regret. This paper first shows that there exists a regret-maximising solution in which all uncertain costs are at a bound, and then uses this to derive an MIP formulation that maximises the regret of a candidate solution. Computational experiments demonstrate that this approach is effective for problems with up to 50 uncertain objective function coefficients, significantly improving upon the existing enumerative method.