Heuristic solutions to robust variants of the minimum-cost integer flow problem
This work addresses uncertainty in network flow optimization for operations research, but it is incremental as it applies existing heuristic methods to new robust variants.
The paper tackles robust variants of the minimum-cost integer flow problem with uncertain arc costs, showing they are NP-hard and proposing heuristics based on local search or evolutionary computing for experimental evaluation.
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.