Contents
We start this chapter by recalling the formulation of a deterministic combinatorial optimization problem, that is the one in which all the input parameters are precisely known. We also present some well known, special cases of this problem like minimum spanning tree, minimum selecting items, shortest path, minimum assignment and minimum cut. We introduce then the minmax regret combinatorial optimization problem with interval data, which can be viewed as a generalization of the deterministic problem where the imprecision is taken into account.We also discuss some closely related problems. In particular we consider some other robustness criteria which can be applied to the interval uncertainty representation.