Algorithms for the min-max regret generalized assignment problem with interval data

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders’ decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.