  We consider binary integer programming problems with the min-max regret
objective function under interval objective coefficients. We propose a new
heuristic framework, which we call the iterated dual substitution (iDS)
algorithm. The iDS algorithm iteratively invokes a dual substitution heuristic
and excludes from the search space any solution already checked in previous
iterations. In iDS, we use a best-scenario-based lemma to improve performance.
We apply iDS to four typical combinatorial optimization problems: the knapsack
problem, the multidimensional knapsack problem, the generalized assignment
problem, and the set covering problem. For the multidimensional knapsack
problem, we compare the iDS approach with two algorithms widely used for
problems with the min-max regret criterion: a fixed-scenario approach, and a
branch-and-cut approach. The results of computational experiments on a broad
set of benchmark instances show that the proposed iDS approach performs best on
most tested instances. For the knapsack problem, the generalized assignment
problem, and the set covering problem, we compare iDS with state-of-the-art
results. The iDS algorithm successfully updates best known records for a number
of benchmark instances.
