A Simulated Annealing Approach for the Minmax Regret Path Problem
Pérez, Francisco, Alfredo Candia-Véjar, César A. Astudillo, Matthew Bardeen · 2014
We propose a novel neighbor generation method for a Simulated Annealing (SA) algorithm used to solve the Minmax Regret Path problem with Interval Data, a difficult problem in Combinatorial Optimization. The problem is defined on a graph where there exists uncertainty in the edge lengths; it is assumed that the uncertainty is deterministic and only the upper and lower bounds are known. A worst-case criterion is assumed for optimization purposes. The goal is to find a path s-t, which minimizes the maximum regret. The literature includes algorithms that solve the classic version of the shortest paths problem efficiently. However, the variant that we study in this manuscript is known to be NP-Hard. We propose a SA algorithm to tackle the aforementioned problem, and we show that our implementation is able to find good solutions in reasonable times for large size instances. Furthermore, a known exact algorithm that utilizes a Mixed Integer Programming (MIP) formulation was implemented by using a commercial solver (CPLEX 1 ). We show that this MIP formulation is able to solve instances up to 1000 nodes within a reasonable amount of time.