Minmax regret solutions for minimax optimization problems with uncertainty

We propose a general approach for finding minmax regret solutions for a cla ss of combinatorial optimization problems with an objective function of min imax type and uncertain objective function coefficients. The approach is ba sed on reducing a problem with uncertainty to a number of problems without uncertainty. The method is illustrated on bottleneck combinatorial optimiza tion problems, minimax multifacility location problems and maximum weighted tardiness scheduling problems with uncertainty. (C) 2000 Published by Else vier Science B.V. All rights reserved.