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.
翻译:本文论述对网络流动适用的稳健优化,考虑了最低成本整流问题的两个稳健的变体。因此,问题配方的不确定性限于弧单位成本,并以一组有限的明确设定的假设情况表示。这表明,两种问题变体都是硬的NP。为了解决所考虑的变体,提出了若干基于本地搜索或进化计算法的累进法。在适当的问题实例中,对累进法进行了实验性评估。