Robust Discrete Optimization for the Minimum Cost Flow Problem

The problem that finding the minimum cost flow in uncertain environments is become more and more outstanding. The cost coefficient is generally vague in many actual cases. This paper discusses the minimum cost flow problem with uncertain cost that is studied by the robust optimization of network. In order to avoid risk, the definition of the robust optimal solution of the minimum cost flow is first put forward and the optimization model of robust deviation minimum cost flow problem (RDMCFP) is established. And we propose an algorithm for RDMCFP, which is able to solute the robust deviation minimum cost flow and the robust deviation minimum cost maximum flow by the enlightenment of the successive shortest path algorithm for minimum cost flow problem. At last, numerical simulation results show the performance of the algorithm in random networks.