  This paper deals with robust optimization applied to network flows. Two
robust variants of the minimum-cost integer flow problem are considered.
Thereby, uncertainty in problem formulation is limited to arc unit costs and
expressed by a finite set of explicitly given scenarios. It is shown that both
problem variants are NP-hard. To solve the considered variants, several
heuristics based on local search or evolutionary computing are proposed. The
heuristics are experimentally evaluated on appropriate problem instances.
