An iterated dual substitution approach for the min-max regret multidimensional knapsack problem

We consider the multidimensional knapsack problem (MKP) with min-max regret criterion under interval profits. We examine three typical algorithms widely applied for min-max regret criterion: fixed-scenario approach, Benders-like decomposition and branch-and-cut. We further propose a new heuristic framework, which we call the iterated dual substitution algorithm. Computational experiments on a wide set of bench-mark instances are carried out, and the proposed iterated dual substitution algorithm performs best on all of the tested instances.