Budget-constrained minimum cost flows

We study an extension of the well-known minimum cost flow problem in which a second kind of costs (called usage fees) is associated with each edge. The goal is to minimize the first kind of costs as in traditional minimum cost flows while the total usage fee of a flow must additionally fulfill a budget constraint. We distinguish three variants of computing the usage fees. The continuous case, in which the usage fee incurred on an edge depends linearly on the flow on the edge, can be seen as the \(\varepsilon \)-constraint method applied to the bicriteria minimum cost flow problem. We present the first strongly polynomial-time algorithm for this problem. In the integral case, in which the fees are incurred in integral steps, we show weak \({\mathcal {NP}}\)-hardness of solving and approximating the problem on series-parallel graphs and present a pseudo-polynomial-time algorithm for this graph class. Furthermore, we present a PTAS, an FPTAS, and a polynomial-time algorithm for several special cases on extension-parallel graphs. Finally, we show that the binary case, in which a fixed fee is payed for the usage of each edge independently of the amount of flow (as for fixed cost flows—Hochbaum and Segev in Networks 19(3):291–312, 1989), is strongly \({\mathcal {NP}}\)-hard to solve and we adapt several results from the integral case.

1. As it is common when dealing with network flow problems, we assume throughout the paper that all of these values are integral, which is no restriction for most of the applications since we can multiply all values with their least common denominator in case of rational data (cf., e.g., Ahuja et al. 1993).

2. Note that the enhanced capacity scaling algorithm as introduced in Ahuja et al. (1993) is designed for graphs without parallel edges and runs in \({\mathcal {O}}(m \log n (m + n \log n))\) time. Nevertheless, it can be shown that this running time worsens only slightly to the claimed one if we allow parallel edges.

3. We refer to Ehrgott (2005) for an in-depth treatment of bicriteria optimization problems and efficient solutions.

4. Note that the values \(A_G(c,b,f)\) computed by our procedure are actually only correct under the additional restriction that the flow is positive only on shortest paths in \(G_y\) for some upgrade profile \(y\). Hence, our procedure may output \(A_G(c,b,f)=+\infty \) in some cases even though the value is actually finite. Nevertheless, by the above argument and since we always minimize over \(c, b\), and \(f\) in each step of the algorithm, we compute \(A_G(c,b,f)\) correctly for each triple of values \(c,b,f\) that correspond to an optimal flow that is positive only on shortest paths for some upgrade profile in a considered component.

5. We assume that \( \left\lfloor \frac{b}{b_e} \right\rfloor = +\infty \) if \(b_e=0\).

We thank the anonymous referees for their valuable comments and suggestions. Furthermore, we thank Stefan Schwarz for his suggestions on the proof of Theorem 8. This work was partially supported by the German Federal Ministry of Education and Research within the project “SinOptiKom—Cross-sectoral Optimization of Transformation Processes in Municipal Infrastructures in Rural Areas”.

Authors and Affiliations

1. Department of Mathematics, University of Kaiserslautern, Paul-Ehrlich-Str. 14, 67663, Kaiserslautern, Germany

   Michael Holzhauser, Sven O. Krumke & Clemens Thielen

Corresponding author

Correspondence to Michael Holzhauser.

Reprints and permissions