Minmax regret combinatorial optimization problems with investments

A new minmax regret optimization model in a system with uncertain parameters is proposed. In this model it is allowed to make investments before a minmax regret solution is implemented in order to modify the source or the nature of the existing uncertainty. Therefore, it is allowed to spend resources in order to change the basic cost structure of the system and take advantage of the modified system to find a robust solution. Some properties of this model allow us to have proper Mathematical Programming formulations that can be solved by standard optimization packages. As a practical application we consider the shortest path problem in a network in which it is possible to modify the uncertainty intervals for the arc costs by investing in the system. We also give an approximate algorithm and generalize some existing results on constant factor approximations.