Minimum cost flow problem with priority

In this paper the minimum cost flow problem in which some subset of arcs have priority to carry flow is analyzed. Because of non-network constraints (side constraint), such problems may not be solved by the known network flow algorithm. Hence, we first construct an LP model for the problem. In the case of integer variables, there is a deep gap between the resulting LP and ILP models. We will show that the ILP problem is NP-hard. For the LP case we develop an algorithm to solve it using thevolume algorithm.

Keywords:

Network flow , Minimum cost , Side constraint , Volume algorithm