A minimum expected regret model for the shortest path problem with solution-dependent probability distributions

• A model for the optimization of a system under uncertainty is proposed and applied to SPP.
• Some properties are stated.
• Mathematical programming formulations are derived from the properties.
• An approximation algorithm is studied.

We consider an optimization problem in which the cost of a feasible solution depends on a set of unknown parameters (scenario) that will be realized. In order to assess the cost of implementing a given solution, its performance is compared with the optimal one under each feasible scenario. The positive difference between the objective values of both solutions defines the regret corresponding to a fixed scenario. The proposed optimization model will seek for a compromise solution by minimizing the expected regret where the expectation is taken respect to a probability distribution that depends on the same solution that is being evaluated, which is called solution-dependent probability distribution. We study the optimization model obtained by applying a specific family of solution-dependent probability distributions to the shortest path problem where the unknown parameters are the arc lengths of the network. This approach can be used to generate new models for robust optimization where the degree of conservatism is calibrated by using different families of probability distributions for the unknown parameters.