Robust minimum cost flow problem under consistent flow constraints

Büsing, Christina; Koster, Arie M. C. A.; Schmitz, Sabrina Article — Published Version Robust minimum cost flow problem under consistent flow constraints Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Büsing, Christina; Koster, Arie M. C. A.; Schmitz, Sabrina (2021) : Robust minimum cost flow problem under consistent flow constraints, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 312, Iss. 2, pp. 691-722, https://doi.org/10.1007/s10479-021-04426-0 This Version is available at: https://hdl.handle.net/10419/287204 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Annals of Operations Research (2022) 312:691–722 https://doi.org/10.1007/s10479-021-04426-0 ORIGINAL RESEARCH Robust minimum cost flow problem under consistent flow constraints Christina Büsing1·Arie M. C. A. Koster1·Sabrina Schmitz1 Accepted: 10 November 2021 / Published online: 28 December 2021 © The Author(s) 2021 Abstract The robust minimum cost flow problem under consistent flow constraints (RobMCF≡)is a new extension of the minimum cost flow (MCF) problem. In the RobMCF≡problem, we consider demand and supply that are subject to uncertainty. For all demand realizations, however, we require that the flow value on an arc needs to be equal if it is included in the predetermined arc set given. The objective is to find feasible flows that satisfy the equal flow requirements while minimizing the maximum occurring cost among all demand realizations. In the case of a finite discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem in networks with integral demands, supplies, and capacities. In particular, the Integral Flow Theorem of Dantzig and Fulkerson does not hold. For this reason, we require integral flows in the entire paper. We show that the RobMCF≡problem is strongly NP-hard on acyclic digraphs by a reduction from the (3,B2)-Sat problem. Further, we demonstrate that the RobMCF≡problem is weakly NP-hard on series-parallel digraphs by providing a reduction from Partition.If in addition the number of scenarios is constant, we propose a pseudo-polynomial algorithm based on dynamic programming. Finally, we present a special case on series-parallel digraphs for which we can solve the RobMCF≡problem in polynomial time. Keywords Minimum cost flow problem ·Equal flow problem ·Robust flows · Series-parallel digraphs ·Dynamic programming 1 Introduction In this paper, we present a new extension of the minimum cost flow (MCF) problem (Ahuja et al. 1988), which we call the robust minimum cost flow problem under consistent flow constraints (RobMCF≡). This problem is motivated by, for example, long-term decisions BSabrina Schmitz [email protected] Christina Büsing [email protected] Arie M. C. A. Koster [email protected] 1Lehrstuhl II für Mathematik, RWTH Aachen University, Pontdriesch 10-12, 52062 Aachen, Germany 123 692 Annals of Operations Research (2022) 312:691–722 in logistic applications. A major problem in logistics is the cost-efficient transport of commodities. Typically, this problem is represented by an MCF model, where a commodity can be identified by a flow sent through a network from a supply source to a sink with demand. In this way, a company can easily assess whether the available means of transport are sufficient for a given demand. If this is not the case, additional transport by subcontractors can be arranged. Such arrangements are generally agreed by long-term contracts, however, the demand is naturally subject to uncertainty. For this reason, valid and cost-efficient decisions have to be made without the knowledge of the actual demand. The problem described can be represented by an adjusted integral MCF model subject to demand uncertainty. We represent the demand uncertainty by a discrete number of possible occurring demand scenarios. In addition to the network requirements of the MCF problem, we are given a predetermined set of arcs referred to as fixed arcs. The flow value on the fixed arcs is supposed to represent the transport by subcontractors. Thus, we require the flow value on a fixed arc to be equal among all demand scenarios. For finding a robust solution to this problem, we minimize the maximum cost that may occur among all demand scenarios. In summary, for the RobMCF≡problem, we consider different demand scenarios for which we require integral flows whose flow values are equal on the respective fixed arcs with the objective of minimizing the maximum cost. The main contribution of this paper can be summarized as follows. We show that most of the knowledge of the MCF problem is not readily transferable to the RobMCF≡problem. In particular, the integrality requirement of the RobMCF≡problem is necessary, even though the demands and supplies of all demand scenarios and the network’s capacities are integral, as Dantzig and Fulkerson’s Integral Flow Theorem (Korte et al. 2012) does not hold. We further prove that finding a feasible solution to the RobMCF≡problem is strongly NP- complete on acyclic digraphs, even if only two demand scenarios and unit arc capacities are considered. On series-parallel digraphs, we show that the decision version of the RobMCF≡ problem is weakly NP-complete and in the special case of a constant number of scenarios it is solvable in pseudo-polynomial time by dynamic programming. If all demand scenarios have the same single source and sink, we propose an algorithm running in polynomial time on series-parallel digraphs. The outline of this paper is as follows. We start with an overview about related work in Sect. 2. Subsequently, in Sect. 3, we give an explicit mathematical problem description, and introduce the notations of this paper. Furthermore, we present first structural results of the problem. In Sect. 4, the problem’s complexity is analyzed on acyclic digraphs. Afterwards, we consider the RobMCF≡problem on series-parallel digraphs in Sect. 5. We conclude this paper by Sect. 6. 2 Related work In the context of logistic applications, several extensions to the MCF problem are analyzed in the literature. We refer to the minimum cost flows with minimum quantities problem introduced by Seedig (2011) and generalized by Krumke and Thielen (2011). In addition to the requirements of the MCF problem, on each arc the flow must either take the value zero or a minimum quantity given. This can be altered and transfered to the case where the flow on the fixed arcs, which represents the transport by subcontractors, takes a minimum value (among all demand scenarios). Another extension is obtained, for example, by the MCF version of the maximum flow problem with disjunctive constraints studied by Pferschy and Schauer (2013). 123 Annals of Operations Research (2022) 312:691–722 693 A maximum flow is sought whose flow value is positive for at least one arc of every arc pair included in a predetermined arc set. Thus, at least one transport performed by subcontractors can be modeled. We point out that the problems above are only considered for one demand scenario, whereas we consider several demand scenarios in the RobMCF≡problem. Due to the equal flow requirements for the fixed arcs, we focus in the following on extensions in the literature with equal flow requirements. Afterwards, we give a short overview of robust network approaches with demand uncertainty. To the best of our knowledge, no study combines equal flow requirements with robust network approaches. Sahni (1974) introduces a variant of the maximum flow (MF) problem (Ahuja et al. 1988), the so-called integral flow with homologous arcs problem (homIF). In addition to the setup of the MF problem, predetermined sets of arcs are given in this problem. A maximum integral flow is sought whose flow value is equal on all arcs that are contained in the same predetermined arc set. Sahni proves the NP-hardness of the problem by a reduction from the Non- Tautology problem. Johnson and Garey (1979) point out that by modifying a construction of Even et al. (1975), the problem’s NP-hardness holds even if all arc capacities areequaltoone.Furthermore,unlessP=NP,thenon-existenceofa2n(1−ε)-approximation algorithm for any fixed ε>0 (on a digraph with nvertices) is proven by Meyers and Schulz (2009) even if a nonzero solution is guaranteed to exist. The MCF version of the homIF problem can be found in the literature as (integer) equal flow problem (EF).Usingstandardtechniques,thecomplexityresultscanbetransformedfrom theMFtotheMCFversion(Ahujaetal.1988).Thereareseveralspecialcasesandapplications for both the MF and MCF version of the problem considered in the literature (Calvete 2003; Meyersand Schulz 2009;Morrisonetal.2013;Srinathan etal.2002).Forinstance,thespecial case of the EF problem where all sets have cardinality two, i.e., an integral MCF is sought whose flow value is equal on a predetermined set of arc pairs, is investigated by Ali et al. (1988). The problem finds application in, for example, crew scheduling (Carraresi and Gallo 1984). Therefore, Ali et al. present a heuristic algorithm based on Lagrangian relaxation. Meyers and Schulz (2009) refer to this problem as paired integer equal flow problem (pEF) and prove that there exists no 2n(1−ε)-approximation algorithm for any fixed ε>0(ona digraph with nvertices), unless P=NP. The statement holds true even if a nontrivial solution is guaranteed to exist. A simpler and in polynomial time solvable special case of the EF problem is the so-called simple equal flow problem (sEF), which is introduced by Ahuja et al. (1999). The sEF problem requires the same but not necessarily integral flow value on only a single predetermined set of arcs. The problem is motivated by the management of water resource systems (Manca et al. 2010). For this purpose, Ahuja et al. (1999)develop several efficient algorithms to solve large-scale instances—a network simplex, a parametric simplex, a combinatorial parametric, a binary search, and a capacity scaling algorithm. These algorithms can easily be modified to obtain integral solutions. Unlike the previous research on MF and MCF problems with equal flow requirements, we consider in the RobMCF≡problem not one demand scenario only, but several demand scenarios. For each of these scenarios, a feasible flow is sought. Furthermore, among all of these scenarios, we require the same flow value on an arc if it is included in the single predetermined set of fixed arcs. Although we consider several demand scenarios, the problem of finding a feasible solution to the RobMCF≡problem can be modeled as a special case of the EF and pEF problem by means of graph copies. We point out that the equal flow requirements in the RobMCF≡problem are only of importance while considering different demand scenarios, i.e., the flow value of a fixed arc has to be equal among all scenarios. In turn, the flow value of two fixed arcs may differ in one scenario. For this reason, the problem of finding a feasible solution to the RobMCF≡problem cannot be modeled as the 123 694 Annals of Operations Research (2022) 312:691–722 sEF problem, except for the special case where the predetermined arc set contains only one arc. Moreover, due to different objectives, the correspondence from the RobMCF≡problem to the EF,sEF,andpEF problem only holds for finding a feasible solution. Demand uncertainty is studied more frequently in the context of network design and network engineering in telecommunication or road networks for example. In robust network design, we have to decide on the capacities such that in all considered scenarios, the entire demand can simultaneously be routed. The cost of installing the capacities is supposed to be minimized. In the single commodity case which was first studied by Minoux (1989) and by Sanità (2009), the flow between supply and demand vertices may differ among the scenarios as long as the capacities are satisfied. For discrete scenarios, a cut-based integer linear program formulation with a separation algorithm is proposed by Álvarez-Miranda et al. (2012). Cacchiani et al. (2016) present a branch-and-cut algorithm for two types of uncertainty sets, a discrete set of scenarios, and a polytope. Atamtürk and Zhang (2007) present a two-stage robust optimization approach where some capacity decisions have to be made before, and other after the demand realization. The decisions have to guarantee that in any case the demand can be routed through the network. In the multi-commodity case, several studies propose different models and uncertainty sets. For instance, Altin et al. (2007,2011) propose the so-called Hose uncertainty model, Belotti et al. (2008) in the context of statistical multiplexing, and Koster et al. (2013)the budget uncertainty set introduced by Bertsimas and Sim (2003,2004). In these studies, the flow is sent proportionally with the demand. In case the flow can be adapted to the demand, a two-stage robust approach is followed. While Mattia (2013) studies dynamic routing, Poss and Raack (2013) suggest to use affine recourse options. 3 Robust minimum cost flow problem under consistent flow constraints 3.1 Definition and notation The RobMCF≡problem is an extension of the MCF problem where supply and demand are subject to uncertainty. The uncertainty is represented by a finite set of discrete scenarios  where we do not have any knowledge which scenario is realized. Considering these scenarios, we are given a digraph G =(V,A)with vertex set Vand arc set A.ThesetofarcsAis defined by two disjoint sets, i.e., A=Afix ∪Afree, where we refer to arcs of set Afix as fixed arcs and arcs of set Afree as free arcs. We use the notation V(G),A(G),Afix(G), and Afree(G)to indicate the sets of vertices, arcs, fixed arcs, and free arcs of digraph G, respectively. Independent of the scenarios arc capacities u :A(G)→Z≥0and arc cost c : A(G)→Z≥0are given. In contrast, vertex balances bλ:V(G)→Zwith v∈Vbλ(v) =0 that define the supply and demand realizations are given for every scenario λ∈, denoted by b=(b1,...,b||). A positive balance indicates a source while a negative balance indicates asink. Note that, in general, the source (sink) vertices do not necessarily have to be the same in every scenario. In case that each scenario has only one vertex with a positive (negative) balance, we refer to these sources as single sources (sinks). If the single sources (sinks) are defined by the same vertex for every scenario, we say that the problem has a unique source (sink). Combined, we obtain the network (G,u,c,b). 123 Annals of Operations Research (2022) 312:691–722 695 Considering only a single scenario λ∈, analogues to the MCF problem a bλ-flow is defined by a function fλ:A(G)→Z≥0that satisfies the capacity constraints 0≤fλ(a)≤u(a) on all arcs a∈Aand the flow balance constraints  a=(v,w)∈A fλ(a)− a=(w,v)∈A fλ(a)=bλ(v) at every vertex v∈V. The cost of a bλ-flow fλis defined by c(fλ)= a∈A c(a)·fλ(a). To consider a set of scenarios , we need to introduce a new definition of a flow, a so called robust b-flow. Definition 1 (Robust Flow) Given a network (G=(V,A=Afix ∪Afree), u,c,b),arobust b-flow f=(f1,..., f||)is defined by a ||-tuple of bλ-flows fλ:A(G)→Z≥0that satisfy the consistent flow constraints fλ(a)=fλ(a)on all fixed arcs a∈Afix for all scenarios λ,λ∈. The cost of a robust b-flow fis defined by the maximum flow cost among all scenarios, i.e., c(f)=maxλ∈c(fλ). We refer to the flow value on an arc of set Afix as its load. Accordingly, the consistent flow constraints are satisfied if the load of a fixed arc is equal in every scenario. The RobMCF≡ problem can finally be formulated as follows. Definition 2 (RobMCF≡) Given a network (G=(V,A=Afix ∪Afree), u,c,b),therobust minimum cost flow problem under consistent flow constraints (RobMCF≡)aimsarobust b-flow f=(f1,..., f||)of minimum cost. Note that in case of a single scenario, i.e., ||=1, the RobMCF≡problem corresponds to the MCF problem. Otherwise, however, there are major differences as the following section shows. 3.2 Structural results In this section, we present structural results of the RobMCF≡problem. In particular, differences to the MCF problem are pointed out where the main difference is the following. Given a network with integral capacities and balances, by Dantzig and Fulkerson (Korte et al. 2012) there always exists an optimal integral flow for the MCF problem. This useful integral flow property is assumed to be given in most studies. However, the integral flow property does not hold for the RobMCF≡problem as the following example shows. Example 1 For a set of two scenarios ={1,2},letanetwork(G,u,c,b)with capacity u≡1 be given, where digraph G, its cost c, and the non-zero balances bare visualized in Fig. 1a. An optimal integral robust b-flow f=(f1,f2)is defined by a first scenario flow f1that sends one unit along path v1v3v5v8, and a second scenario flow f2that sends one unit each along path v1v3v5v6and v1v4v5v7v6. This results in cost of c(f)=4asc(f1)=4 and c(f2)=2+0=2 hold true. However, by neglecting the integral flow requirement, there exists a robust b-flow ˜ f= (˜ f1,˜ f2)with cost of c(˜ f)=3. Flow ˜ f1sends a half unit each along paths v1v3v5v8 123 696 Annals of Operations Research (2022) 312:691–722 Fig. 1 aA non-integral robust b-flow is the only optimal solution bA scenario flow that does not send the maximum demand among all scenarios causes the maximum cost in a unique source, unique sink network and v1v4v5v8ending up in total cost of c(˜ f1)=3. Flow ˜ f2sends a half unit each along paths v1v2v5v6and v1v3v5v6, and one unit along path v1v4v5v7v6, also ending up in cost of c(˜ f2)=3. Corollary 1 Considering the continuous relaxation of the RobMCF≡problem, there does not always exist an integral robust flow with minimum cost, even if all capacities and balances are integral. We note that if no integer requirements for a robust flow are given, the RobMCF≡problem canbesolvedbyasimplelinearprogram(LP)inpolynomialtimein|V|,|A|and||.However, as applications of the RobMCF≡problem often require integral flow values, hereafter this paper only concentrates on integral solutions. Further motivated by applications, in the next step, we investigate the RobMCF≡problem where either the load of the fixed arcs is given, or the number of fixed arcs is constant. In logistics for example, this complies with finding a solution of minimum cost if the transport is already contractually agreed or limited. The following results show that we can solve these special cases in polynomial time. Lemma 1 Let I=(G=(V,A=Afix ∪Afree), u,c,b)be a RobMCF≡instance. For a given load :Afix(G)→Z≥0, an optimal robust b-flow fthat satisfies f λ(a)=(a)for all fixed arcs a ∈Afix(G)in every scenario λ∈can be computed in polynomial time if one exists. Proof We transform instance Ito ||simple minimum cost ˜ bλ-flow instances  Iλ= ( G,u,c,˜ bλ)that can be considered for every scenario λ∈separately. Instances  Iλ, λ∈are obtained by deleting the fixed arcs from digraph Gresulting in digraph  G, i.e.,  G=G−Afix, while at the same time the new balances ˜ bλ:V( G)→Zare defined as follows ˜ bλ(v) =bλ(v) + a=(w,v)∈Afix(G) (a)− a=(v,w)∈Afix(G) (a). After computing minimum cost ˜ bλ-flows ˜ fλfor all instances  Iλ,λ∈, a corresponding robust b-flow f=(f1,..., f||)for instance Iis defined as fλ(a)=(a)for all fixed arcs a∈Afix(G), ˜ fλ(a)for all free arcs a∈Afree(G), 123 Annals of Operations Research (2022) 312:691–722 697 and causes cost of c(f)=max λ∈c(˜ fλ)+ a∈Afix(G) c(a)·(a). Assume the constructed robust b-flow fis not optimal, i.e., a robust b-flow ˆ f= (ˆ f1,..., ˆ f||)exists with cost c(ˆ fλ1)=max λ∈c(ˆ fλ)=c(ˆ f)<c(f)=max λ∈c(fλ)=c(fλ2) for scenarios λ1,λ 2∈.Let fλdenote the flow which results from restricting the scenario flow ˆ fλof instance Ito instance  Iλ,λ∈. As the load on the fixed arcs is given, the values of flows ˆ fand fon the fixed arcs are equal for every scenario, i.e., ˆ fλ(a)=fλ(a)=(a) for a∈Afix and λ∈. Using this insight, we obtain c(ˆ fλ1)<c(fλ2) ⇔ a∈A(G) c(a)ˆ fλ1(a)<  a∈A(G) c(a)fλ2(a) ⇔ a∈Afree(G) c(a)ˆ fλ1(a)<  a∈Afree(G) c(a)fλ2(a) ⇔c(fλ1)<c(˜ fλ2). Furthermore, as by definition flow ˆ fsatisfies the consistent flow constraints, c(fλ1)= maxλ∈c(fλ)is implied by c(ˆ fλ1)=maxλ∈c(ˆ fλ). Overall, we obtain c(˜ fλ2)>c(fλ1)=max λ∈c(fλ)≥c(fλ2), which is a contradiction to the fact that flow ˜ fλ2is an optimal ˜ bλ2-flow for instance  Iλ2. Considering the runtime, the transformation of instance Ito instances  I,λ∈is done in O(||·|A|)time. Subsequently, a minimum cost ˜ bλ-flow ˜ fλcan be computed for every scenario λ∈by, for example, the Minimum Mean Cycle-Canceling Algorithm in O(|A|3|V|2log |V|)time (Korte et al. 2012). Hence, an optimal robust b-flow can be computed in O(||·|A|3·|V|2log |V|)total time. Note that if for a scenario λ∈no feasible ˜ bλ-flow exists, there also does not exist a robust b-flow. Corollary 2 The RobMCF≡problem is solvable in polynomial time for a constant number of fixed arcs. Proof We formulate the RobMCF≡problem as LP where we only require the constant number of variables that indicate the load on the fixed arcs to be integral. The resulting mixed integer linear program (MIP) can be solved in polynomial time by Lenstra’s algorithm (1983). In the case that the resulting robust flow is not integral, we define a load by the value of the MIP’s integer variables. Analogous to the proof of Lemma 1, we transform the instance and compute an optimal integral robust flow in polynomial time. At the end of this section, we focus on the objective function of the RobMCF≡problem. From the MCF problem, or the multi-commodity flow problem (Korte et al. 2012), we know that due to different sources and sinks a flow that sends one unit may cause higher cost than a flow sending two units. Obviously, the same property remains true for instances of the RobMCF≡problem. If we consider the RobMCF≡problem on networks with a unique 123 698 Annals of Operations Research (2022) 312:691–722 source and a unique sink, we might assume, analogous to the MCF problem, that the cost of a robust flow is determined by the scenario flow which sends the maximum demand. However, the following example shows that this is not true. Example 2 For a set of two scenarios ={1,2},letanetwork(G,u,c,b)with capacity u≡1 be given, where digraph G, its cost c, and the non-zero balances bare visualized in Fig. 1b. The only feasible and therefore also optimal solution f=(f1,f2)to the RobMCF≡ problem is easy to determine. Considering the second scenario flow f2first, the only option to send two flow units from source sto sink tis along paths sv1tand sv2tdue to the capacity constraints. As the second scenario flow f2uses both fixed arcs, the first scenario flow f1must also send flow along these arcs. For this reason, the only option to send one flow unit from source sto sink tis along path sv2v1t. The cost of the robust b-flow fis c(f)=c(f1)=100. Corollary 3 In a network with a unique source and a unique sink, the cost of a robust b-flow is not necessarily determined by the bλ-flow which sends the maximum demand among all scenarios λ∈. As a result, independent of the number of sources and sinks given, for solving the RobMCF≡problem, we cannot only concentrate on a single scenario. However, by reason of the following lemma, in a network with a unique source and a unique sink it is sufficient to concentrate on two scenarios only, namely those in which the minimum and maximum demand is sent. Lemma 2 Let I=(G=(V,A=Afree ∪Afix), u,c,b)be a RobMCF≡instance with a unique source s and a unique sink t. Without loss of generality, let the scenarios λ∈ be strictly ordered in ascending order of their supply balances bλ, i.e., b1(s)<b2(s)< ...<b||(s). Further, let feasible integral bλ-flows f λfor scenarios λ=1and λ=||be given that satisfy the consistent flow constraints, i.e., f 1(a)=f||(a)for a ∈Afix.Arobust b-flow f=(f1,..., f||)with cost of c(f)=max{c(f1), c(f||)}can be computed in polynomial time. Proof As we consider a network with a unique source and a unique sink, a feasible robust b-flow ffor instance Iis given by the convex combination of the flows f1and f||as follows. For every scenario λ∈\{1,||} let γλ∈[0,1]be a parameter such that bλ(s)=γλ·b1(s)+(1−γλ)·b||(s) holds. We define the corresponding scenario flows fλ,λ∈\{1,||} by fλ(a):= γλ·f1(a)+(1−γλ)·f||(a) for all arcs a∈A. Flows fλ,λ∈\{1,||} satisfy the capacity and flow balance constraints, but may be non-integral on some free arcs. Therefore, we restrict every bλ-flow fλ,λ∈\{1,||} to the respective MCF instance  Iλobtained analogous to the Proof of Lemma 1, and this results in feasible ˜ bλ-flows denoted by ˜ fλ.Let ˜ fλ OPT be an optimal integral ˜ bλ-flow for instance  Iλ,λ∈\{1,||},thenc(˜ fλ OPT)≤c(˜ fλ)holds true. For all scenarios λ∈\{1,||},flows ˜ fλ OPT and ˜ fλcan be retransformed to flows fλ OPT, and respectively, fλof instance I, ending up in cost of 123 Annals of Operations Research (2022) 312:691–722 705 c(f1)= a∈A c(a)f1(a)= a∈Afix c(a)f1(a)+ a∈Afree c(a)f1(a)=w+2w=3w. Accordingtoflow f1and the partition, we define the second scenario flow f2by f2(a)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1forallarcsa=a2 i∈Aif si∈S2, 1forallarcsa=a3 i∈Aif si∈S1, 1forarca=an+1∈A, 0 otherwise, i.e., flow f2sends exactly one unit from source v0to sink talong arcs of paths p2and p3, and by using arc an+1. The following cost is caused c(f2)= a∈A c(a)f2(a) = a∈Afix c(a)f2(a)+ a∈Afree\{an+1} c(a)f2(a)+c(an+1)f2(an+1) =w+0+2w=3w. Consequently, we have constructed a robust b-flow f=(f1,f2)with cost of 3w. Conversely, let f=(f1,f2)be a robust b-flow with cost of at most 3w, i.e., c(f)= max{c(f1), c(f2)}≤3w. The first scenario flow f1sends two units from source v0to sink vn. Due to the capacities, not only a single path is used to send these flow units. In particular, not only path p3causing zero cost is used. As sending one flow unit along path p1would cause cost of c(p1)= a∈A(p1) c(a)= n  i=1 2si=4w>3w≥max{c(f1), c(f2)}, flow f1does not use all arcs of path p1either. Accordingly, flow f1uses as many arcs of path p2as at least cost of wis caused in order that at most 2wcost is caused due to arcs of path p1. The second scenario flow f2sends one unit from source v0to sink t.Asflow f2uses arc anwith cost of 2wto reach sink t, the unit is sent along arcs of paths p1,p2,p3such that at most cost of wis caused. Furthermore, as flow f1uses as many arcs of path p2as at least cost of wis caused, this also holds true for flow f2as A(p2)=Afix holds. Consequently, flow f2onlyusesarcsofpathp2and p3, however, due to the acyclic pearl digraph never of the same multi-arc simultaneously such that the sets S1:= {si|f2(a2 i)=1forarca2 i∈Afix with i∈[n]}, S2:= {si|f2(a3 i)=1forarca3 i∈A(p3)with i∈[n]} form a feasible partition for instance I. In the next step, we refute the strong NP-completeness in the special case of a constant number of scenarios. Therefore, we propose a pseudo-polynomial algorithm based on dynamic programming. The dynamic program (DP) is applicable for networks with an arbitrary number of sources and sinks, especially for multiple sources and multiple sinks. The core idea of the DP is a bottom-up method using the SP tree. While composing the SP digraph step by step, in each of these steps a robust flow is sought satisfying additional restrictions explained in the following. The flow needs to send a given supply from the origin through the 123 706 Annals of Operations Research (2022) 312:691–722 subgraph considered in the current step. Further, the flow needs to satisfy the inner vertices’ balances as their in- and outgoing arcs are already set. In contrast, the balances at the origin and target do not have to be satisfied as in subsequent steps further subgraphs can still be composed at these vertices. Moreover, the flow must exactly meet a budget given. Backtracking the steps of the DP results to an optimal robust flow. Before we present the DP in more detail, we introduce the notations and labels needed. Let us consider a RobMCF≡instance (G,u,c,b)where Gis an SP digraph with origin oand target q. Further, let TbetheSPtreeofdigraphGwith its root vertex r∈V(T). We denote the subgraph of digraph Gthat is associated to vertex v∈V(T)by Gv, and its origin and target by ovand qv, respectively. The algorithm relies on demand labels dv(˜ sv,˜ cv) defined for every subgraph Gvassociated with a vertex v∈V(T). The parameter vector ˜ sv=(˜s1 v,...,˜s|| v)∈Z|| ≥0determinesforallscenariosthesupplyatoriginovofsubgraph Gv. For every scenario λ∈the supply ˜sλ vis limited by the sum of the capacities of all outgoing arcs of origin ovof subgraph Gv, i.e., ˜sλ v∈{0,...,Uv}with Uv=a=(ov,w)∈A(Gv)u(a). The parameter vector ˜ cv=(˜c1 v,...,˜c|| v)∈Z|| ≥0specifies for all scenarios the budget that must be spent for sending the supply in subgraph Gvwith respect to cost function c. Consequently, an upper bound on the budget is given by the cost that may occur in subgraph Gv, i.e., ˜cλ v∈{0,...,Cv}for λ∈with Cv=a∈A(Gv)c(a)·u(a). Let the (˜ sv,˜ cv)-restricted robust minimum cost flow problem under consistent flow constraints (rRobMCF≡(˜ sv,˜ cv)) be defined as the RobMCF≡problem on subgraph Gv, v∈V(T)with restrictions implied by supply ˜ svand budget ˜ cv. The demand label dv(˜ sv,˜ cv) is defined as the optimal solution value of the rRobMCF≡(˜ sv,˜ cv)problem. For convenience and for the sake of clarity, we indicate the rRobMCF≡(˜ sv,˜ cv)problem by the following integer program formulation. dv(˜ sv,˜ cv)=min 0 (1) s.t.  a∈A(Gv) c(a)·fλ a=˜cλ v∀λ∈(2)  a=(w,z)∈A(Gv) fλ a− a=(z,w)∈A(Gv) fλ a =bλ(w) if w= ov, ˜sλ wif w=ov,∀w∈V(Gv)\{qv},λ∈(3) fλ a=fλ a∀a∈Afix(Gv), λ, λ∈(4) 0≤fλ a≤u(a)∀a∈A(Gv), λ ∈(5) fλ a∈Z≥0∀a∈A(Gv), λ ∈(6) The rRobMCF≡(˜ sv,˜ cv)problem requires a robust b-flow in subgraph Gvby means of constraints (3)–(6). Therefore, the flow needs to satisfy the supply ˜ svat origin ov,andthe balances bat all other vertices except target qv. Furthermore, the flow must exactly meet the budget ˜ cv, see constraint (2). By definition of the objective function (1), finding a feasible solution is sufficient to solve the rRobMCF≡(˜ sv,˜ cv)problem, i.e., dv(˜ sv,˜ cv)∈{0,∞}. For solving the RobMCF≡problem on SP digraphs, the DP exploits the structure of the SP tree to compute demand labels recursively. More precisely, considering a specific vertex in the SP tree, we update the corresponding demand label based on the labels corresponding to the children’s vertices in a bottom-up procedure. Depending on whether the SP tree’s vertex considered is an L-, S-, or P-vertex, one of the following three procedures is applied. An 123 Annals of Operations Research (2022) 312:691–722 707 example of the procedures of the DP is given in Appendix A. We start with the initialization at the leaves. Lemma 3 Let v∈V(T)be a leaf of SP tree T , i.e., vis an L-vertex. The demand label dv(˜ sv,˜ cv)is initialized by dv(˜ sv,˜ cv)=⎧ ⎨ ⎩ 0if (ov,qv)∈Afree(Gv),˜cλ v=c((ov,qv)) ·˜sλ v,∀λ∈, 0if (ov,qv)∈Afix(Gv),˜sλ v=˜sλ v,˜cλ v=c((ov,qv)) ·˜sλ v,∀λ,λ∈, ∞otherwise. Proof Asv∈V(T)is an L-vertex, subgraph Gvonlyconsistsofthesinglearcav:= (ov,qv). If avis a free arc, i.e., av∈Afree(Gv),˜cλ v=c((ov,qv)) ·˜sλ vmust hold true. Otherwise, there exists no feasible flow that satisfies constraints (2) due to constraints (3). Consequently, the rRobMCF≡(˜ sv,˜ cv)problem is not solvable, i.e., dv(˜ sv,˜ cv)=∞.Ifavis a fixed arc, i.e., av∈Afix(Gv), the constraints of the previous case need to be satisfied due to the same argumentation. In addition, ˜sλ v=˜sλ vmust hold true for all scenarios λ, λ∈by reason of constraints (4). To conclude, if the presented constraints are satisfied, an optimal solution to the rRobMCF≡(˜ sv,˜ cv)problem is given by f(av):= ˜ svsuch that dv(˜ sv,˜ cv)=0 holds true. In the next step, we consider the case in which the demand label is derived recursively from the demand labels of the child vertices that are parallelly composed. Lemma 4 Let v∈V(T)be a P-vertex in SP tree T with child vertices x,y∈V(T).The demand label dv(˜ sv,˜ cv)at vertex vcan be computed by a composition of the demand labels dx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)of its child vertices x and y as follows dv(˜ sv,˜ cv)=min ˜ sv=˜ sx+˜ sy ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy). Proof For vertex v∈V(T),letdv(˜ sv,˜ cv)be the demand label with the related solution f∗.Asvis a P-vertex, flow f∗with associated supply ˜ sv=a=(ov,w)∈A(Gv)f∗(a)can be divided into two flows fxand fywith associated supplies ˜ sxand ˜ sy, respectively. Flow fxis defined on subgraph Gx,andflow fyis defined on subgraph Gyonly. The budget ˜ cv=a∈A(Gv)c(a)·f∗(a)of flow f∗is also divided such that ˜ cxdescribes the budget of flow fxand ˜ cythe budget of flow fy. Flows fxand fyare feasible solutions to the rRobMCF≡(˜ sx,˜ cx)and rRobMCF≡(˜ sy,˜ cy)problem, respectively. Consequently, we obtain dv(˜ sv,˜ cv)=dv(˜ sx+˜ sy,˜ cx+˜ cy)≥dx(˜ sx,˜ cx)+dy(˜ sy,˜ cy), where dx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)are the demand labels corresponding to the child vertices x,y∈V(T). In particular, this implies dv(˜ sv,˜ cv)≥min ˜ sv=˜ sx+˜ sy ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy). Conversely, for child vertices x,y∈V(T),letdx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)be the demand labels with related solutions f∗ xand f∗ y. Combining flows f∗ xand f∗ yresults in a feasible solution fv:= f∗ x+f∗ yto the rRobMCF≡(˜ sv,˜ cv)problem with supply ˜ sv:= ˜ sx+˜ syand budget ˜ cv:= ˜ cx+˜ cy. Consequently, for all supplies ˜ sx,˜ syand budgets ˜ cx,˜ cygiven the following holds true dx(˜ sx,˜ cx)+dy(˜ sy,˜ cy)≥dv(˜ sx+˜ sy,˜ cx+˜ cy)=dv(˜ sv,˜ cv), 123 708 Annals of Operations Research (2022) 312:691–722 where dv(˜ sv,˜ cv)is the demand label corresponding to vertex v∈V(T). This implies dv(˜ sv,˜ cv)≤min ˜ sv=˜ sx+˜ sy ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy). To conclude the computation of demand labels, we consider the case in which a demand label is derived recursively from the demand labels of the child vertices that are serially composed. Lemma 5 Let v∈V(T)be an S-vertex in SP tree T with child vertices x,y∈V(T).The demand label dv(˜ sv,˜ cv)at vertex vcan be computed by a composition of the demand labels dx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)of its child vertices x and y by dv(˜ sv,˜ cv)=min ˜ sx=˜ sv ˜ sy=˜ sx+β ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy), where β=(β1,...,β||)with βλ:= v∈V(Gx)\{ox}bλ(v) holds for every scenario λ∈. Proof For vertex v∈V(T),letdv(˜ sv,˜ cv)be the demand label with the related solution f∗. We assume that digraph Gvis constructed by contracting the target qxof subgraph Gx with the origin oyof subgraph Gy. Consequently, the flow that is sent through subgraph Gy requires on the one hand the access via origin oy. On the other hand, at least the same amount of flow is originated in subgraph Gxin the first place. Using this insight, we partition flow f∗ and the associated supply ˜ sv=a=(ov,w)∈A(Gv)f∗(a)in two flows fxand fywhere flow fxis defined on subgraph Gxand flow fyis defined on subgraph Gyonly. More precisely, we obtain fx(a):= f∗(a)for all arcs a∈A(Gx)with associated supply ˜ sx=˜ sv,and fy(a):= f∗(a)for all arcs a∈A(Gy)with associated supply ˜ sy:= a=(oy,w)∈A(Gy)f∗(a)=˜ sx+β where β=(β1,...,β||)with βλ:= v∈V(Gx)\{ox}bλ(v),λ∈. The associated supply ˜ syresults from the supply ˜ sxplus the flow that originates from sources (that are different from the origin) in subgraph Gxminus the flow that is absorbed at sinks in subgraph Gx.The budget ˜ cv=a∈A(Gv)c(a)·f∗(a)of flow f∗can also be divided such that ˜ cxdescribes the budget of flow fxand ˜ cythe one of flow fy. Flows fxand fyare feasible solutions to the rRobMCF≡(˜ sx,˜ cx)and rRobMCF≡(˜ sy,˜ cy)problem, respectively. Consequently, we obtain dv(˜ sv,˜ cv)=dv(˜ sx,˜ cx+˜ cy)≥dx(˜ sx,˜ cx)+dy(˜ sy,˜ cy), where dx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)are the demand labels corresponding to child vertices x,y∈ V(T). In particular, this implies dv(˜ sv,˜ cv)≥min ˜ sx=˜ sv ˜ sy=˜ sx+β ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy). Conversely, for child vertices x,y∈V(T),letdx(˜ sx,˜ cx)and dy(˜ sy,˜ cy)with ˜ sy=˜ sx+β be the demand labels with related solutions f∗ xand f∗ y. Combining flows f∗ xand f∗ yresults in a feasible solution fv:= f∗ x+f∗ yto the rRobMCF≡(˜ sv,˜ cv)problem with supply ˜ sv:= ˜ sx and budget ˜ cv:= ˜ cx+˜ cy. Consequently, for all supplies ˜ sx,˜ syand budgets ˜ cx,˜ cythe following holds true dx(˜ sx,˜ cx)+dy(˜ sy,˜ cy)≥dv(˜ sx,˜ cx+˜ cy)=dv(˜ sv,˜ cv), 123 Annals of Operations Research (2022) 312:691–722 709 where dv(˜ sv,˜ cv)is the demand label corresponding to vertex v∈V(T). This implies dv(˜ sv,˜ cv)≤min ˜ sx=˜ sv ˜ sy=˜ sx+β ˜ cv=˜ cx+˜ cydx(˜ sx,˜ cx)+dy(˜ sy,˜ cy). Finally, a robust flow in SP digraph Gis obtained by backtracking the steps of the DP, and considering the demand label associated to the SP tree’s root r. Lemma 6 Let fbe an optimal robust b-flow in SP digraph Gr. For the cost it holds that c(f)=min ˆc∃˜ cr∈{0,...,Cr}||:max λ∈˜cλ r=ˆc∧dr(b(or), ˜ cr)=0(7) with Cr=a∈A(Gr)c(a)·u(a). Proof For all vertices v∈V(G)\{q}, the flow balance constraints of the RobMCF≡problem are ensured by constraints (3) of the rRobMCF≡(˜ sr,˜ cr)problem with ˜ sr=b(or).The consistent flow and capacity constraints as well as the integer conditions of the RobMCF≡ problem are one to one included in the rRobMCF≡(˜ sr,˜ cr)problem by constraints (4), (5) and (6), respectively. Accordingly, every feasible solution to the rRobMCF≡(˜ sr,˜ cr)problem is also a feasible solution to the RobMCF≡problem. However, the rRobMCF≡(˜ sr,˜ cr)problem contains one additional set of constraints, namely constraints (2). Constraints (2) control whether the cost of a flow is equal to the budget. For this reason, we look for a budget ˜ cr∈{0,...,Cr}||for which a feasible solution to the rRobMCF≡(˜ sr,˜ cr)problem exists, i.e., for which dr(b(or), ˜ cr)=0 holds true. This solution corresponds to a robust b-flow fwith cost c(f)=maxλ∈c(fλ)=maxλ∈˜cλ r. Therefore, we are interested in the minimum maximum budget needed among all scenarios λ∈which we obtain by expression (7). After all, we analyze the runtime of the DP. Theorem 4 Let (G,u,c,b)be a RobMCF≡instance where G is an SP digraph with origin o. Using the DP described, the RobMCF≡problem can be solved in O(|A(G)|(U+1)2||(C+ 1)2||)time where U := a=(o,v)∈A(G)u(a)and C := a∈A(G)c(a)·u(a)holds. Proof The correctness of the algorithm follows from Lemmas 3–6. Considering the runtime, first of all, we mention that the representation of an SP digraph Gby its SP tree Tcan be computedin O(|A(G)|)(Valdesetal.1979).At everySPtree’svertexv∈V(T)demandlabelsfor all supplies ˜ svand budgets ˜ cvneed to be calculated where the number of combinations is limitedby(U+1)||·(C+1)||.AsSPtreeTof SPdigraph Ghas exactly|V(T)|=2|A(G)|−1 vertices, we have to compute O(2|A(G)|·(U+1)||·(C+1)||)demand labels. It remains to bound the complexity for computing the demand labels. If v∈V(T)is an L-vertex, computing the corresponding demand labels is clearly in O(1).Ifv∈V(T)is an S-or P-vertex, we need to compute the minimum of (U+1)||(C+1)||sums which is in O((U+1)||(C+1)||).Intotal,we obtainaruntimeofO(2|A(G)|·(U+1)2||·(C+1)2||). By reason of Theorem 4, the pseudo-polynomial runtime of the DP follows if the number of scenarios is constant. Together with the result of Theorem 3we obtain the following corollary. Corollary 5 The decision version of the RobMCF≡problem on networks based on SP digraphs with multiple sources and multiple sinks is weakly NP-complete, even if only two scenarios and unit arc capacities are considered on pearl digraphs. If the number of scenarios is not part of the input, the RobMCF≡problem can be solved by the presented DP in pseudo-polynomial time. 123 710 Annals of Operations Research (2022) 312:691–722 5.2 Special case of unique source and unique sink networks In this section, we provide a polynomial time algorithm for the special case of networks based on SP digraphs with a unique source and a unique sink. The core idea of the algorithm is based on the algorithm of Bein et al. (1985) which iteratively sends flow along shortest paths to solve the MCF problem. Before we propose a generalized algorithm for the RobMCF≡ problem, we investigate properties of an optimal robust flow in the networks considered. In particular, we study the cost and show that we can restrict the statement of Lemma 2. We start with introducing the notations and definitions needed. Let us consider a RobMCF≡instance (G,u,c,b)where Gis an SP digraph with origin oand target q.AsSP digraphs are acyclic, we assume without loss of generality that the unique source complies with origin oand the unique sink complies with targetq. Due to Lemma 2, we limit our efforts to a set of two scenarios, i.e., ={1,2}. For convenience, we introduce a demand vector d=(d1,d2), consisting of the number of flow units that, according to the balances b, are supplied from the unique source and demanded by the unique sink, i.e., d1:= b1(o)=−b1(q) and d2:= b2(o)=−b2(q). Without loss of generality, let d1and d2be given such that d1≤d2holds true. Further, let H⊆Gbe an SP subgraph with origin oH. We denote the flow value of a given flow fλ,λ∈entering subgraph Hby δ( fλ |H)such that the following holds δ( fλ |H):=  a=(oH,w)∈A(H) fλ(a). Using these notations and definitions we aim at investigating the cost of an optimal robust flow. In contrasttonetworksbased onacyclicdigraphs withauniquesourceand a uniquesink, see Example 2, for the special case considered in this section it is sufficient to concentrate on the cost of the last scenario flow. Before we prove this statement, we need the following two auxiliary lemmas. Lemma 7 Let G be an SP digraph which is composed by subgraphs G1and G2, and let (G,u,c,b)be a corresponding RobMCF≡instance. There exists an optimal robust b-flow f=(f1,f2)for which δ( f2 |G1)≥δ( f1 |G1)and δ( f2 |G2)≥δ( f1 |G2)hold true. By reason of the consistent flow constraints, the statement is not apparent. Due to the length, the proof is moved to Appendix B. Lemma 8 Let (G,u,c,b)be a RobMCF≡instance where G is an SP digraph. There exists an optimal robust b-flow f=(f1,f2)such that f 2(a)≥f1(a)holds true for all arcs a∈A(G). Proof Let TbetheSPtreeofSPdigraphG. As we consider a digraph with a unique source and a unique sink, the statement of Lemma 7can be recursively transferred to subgraphs Gv⊆Gassociated to the SP tree’s vertices v∈V(T), i.e., δ( f2 |Gv)≥δ( f1 |Gv)for all v∈V(T). Consequently, f2(a)≥f1(a)holds true for all arcs a∈A(G). Notethat,ingeneral,thestatementofLemma8isnottrueforacyclicdigraphsasExample2 shows. We are now able to prove the following crucial lemma regarding the cost of a robust flow. Lemma 9 Let (G,u,c,b)be a RobMCF≡instance where G is an SP digraph. There exists an optimal robust b-flow f=(f1,f2)whose cost is determined by the cost of the last scenario flow, i.e., c(f)=max{c(f1), c(f2)}=c(f2). 123 Annals of Operations Research (2022) 312:691–722 711 Proof By Lemma 8, there exists an optimal robust b-flow f=(f1,f2)such that f2(a)≥ f1(a)holds for all arcs a∈A(G). The scenario flows cause the following cost c(f1)= a∈A c(a)·f1(a)≤ a∈A c(a)·f2(a)=c(f2), from which the statement immediately follows. By reason of Lemma 9, we concentrate on the last scenario in the following. Firstly, we note that a last scenario flow needs to send demand d2−d1in subgraph G−Afix,andwe refer to this demand as excess demand. Before we present a further useful property of the last scenario flow regarding its excess demand and a shortest path in subgraph G−Afix,we need the following auxiliary lemma. Lemma 10 Let G be a series composition of SP digraphs G1and G2, and let Ibe a corresponding RobMCF≡instance. Then, let I1and I2be the RobMCF≡instances which are obtained by restricting instance Ito subgraphs G1and G2, respectively. A solution fto instance Iis optimal if and only if the solutions f|G1and f|G2, which can be obtained by restricting fto subgraphs G1and G2, are optimal to instances I1and I2, respectively. A proof can be found in Appendix B.Example4in Appendix Bshows that the SP property of the digraph is necessary for the truthfulness of Lemma 10. Using Lemma 10,weformulate a useful property for an existing optimal robust flow. Lemma 11 Let G =(V,A=Afix ∪Afree)be an SP digraph with origin o and target q. Further, let I=(G,u,c,b)be a corresponding RobMCF≡instance with demand d= (d1,d2),d2≥d1. With respect to cost c, let p be a shortest (o,q)-path in subgraph G −Afix with its bottleneck value u p=mina∈A(p)u(a). There exists an optimal robust b-flow f= (f1,f2)for which the following holds true f2(a)≥min{up,d2−d1}for all a ∈A(p). (8) Proof We prove the correctness of the statement by induction on the number of the digraph’s arcs m:= |A|. For the beginning, if we consider a digraph consisting of one arc only, the statement is readily apparent. In the next step, we prove the statement for a digraph with m+1 arcs, providing that the statement holds true for all digraphs consisting of at most m arcs. For this purpose, we distinguish between two cases. Firstly, we assume that Gis a series composition of SP digraphs G1and G2. Therefore, the origin of digraph G1and the target of digraph G2are contracted to one vertex that we denote by w. Due to the composition of digraph G,ashortest(o,q)-path pin subgraph G−Afix is composed of a shortest (o,w)-path p1in subgraph G1−Afix, and a shortest (w, q)-path p2in subgraph G2−Afix,seeFig.5a. Considering subgraphs G1and G2separately, we obtain the RobMCF≡instances I1and I2, respectively. By induction hypothesis there exist an optimal robust flow f|G1=(f1 |G1,f2 |G1)in subgraph G1and an optimal robust flow f|G2=(f1 |G2,f2 |G2)in subgraph G2satisfying f2 |G1(a)≥min{up1,d2−d1}for all arcs a∈A(p1), f2 |G2(a)≥min{up2,d2−d1}for all arcs a∈A(p2). By Lemma 10, the composed flow f=(f1,f2)with f1:= f1 |G1+f1 |G2and f2:= f2 |G1+f2 |G2is an optimal robust b-flow in digraph Gwhere the desired property is still satisfied. 123 712 Annals of Operations Research (2022) 312:691–722 (a) (b) Fig. 5 Shortest path pin subgraph G−Afix where digraph Gis a series aor parallel bcomposition Secondly, we assume that Gis a parallel composition of SP digraphs G1and G2. Without loss of generality, let the shortest (o,q)-path pbe contained in subgraph G1−Afix,seeFig. 5b. Further, let f=(f1,f2)be an optimal robust b-flow which sends demand d=(d1,d2) through digraph Gthat satisfies without loss of generality the property of Lemma 7, i.e., δ( f2 |Gi)−δ( f1 |Gi)≥0forGi,i∈{1,2}.Iftheoptimal flow fdoesnot satisfytheproperty(8), applying the following procedure leads to the desired result. We consider the subgraphs G1 and G2separately, resulting in RobMCF≡instances I1and I2, respectively. To define how much demand d|Giis supposed to be sent through subgraph Giof instance Ii, we exploit the partition of demand dof the optimal flow f, i.e., d|Gi=(d1 |Gi,d2 |Gi):= (δ( f1 |Gi), δ( f2 |Gi)) for i∈{1,2}. Considering subgraph G1, by induction hypothesis there exists an optimal robust flow ˜ f=(˜ f1,˜ f2)which sends demand d|G1=(d1 |G1,d2 |G1)and satisfies ˜ f2(a)≥min{up,d2 |G1−d1 |G1}for all arcs a∈A(p). Further, let an optimal robust flow ˆ fbe given which sends demand d|G2through subgraph G2. By composing flows ˜ fand ˆ f,weobtainarobustb-flow f=(f1,f2)with scenario flows f1:= ˜ f1+ˆ f1and f2:= ˜ f2+ˆ f2for instance I.Flow fis optimal as there exists an optimal robust flow with the same partition d|G1and d|G2of demand dbetween subgraphs G1and G2,andasflows ˜ fand ˆ fare optimal themselves. It remains to prove that f2(a)≥min{up,d2−d1}holds for all arcs a∈A(p). We distinguish between the following two cases. Firstly, we consider the case where d2 |G1−d1 |G1≥min{up,d2−d1}holds true. As f2(a)=˜ f2(a)holds for all arcs a∈A(G1)by construction, the desired property results immediately for all arcs a∈A(p)⊆A(G1)as shown by the following f2(a)=˜ f2(a)≥min{up,d2 |G1−d1 |G1} ≥min{up,min{up,d2−d1}} =min{up,d2−d1}. Secondly, we consider the case where d2 |G1−d1 |G1<min{up,d2−d1}holds true. Assume f2(a)<min{up,d2−d1}istrueforonearca∈A(p)⊆A(G1).Weredirectthelastscenario flow f2of robust flow fsuch that demand of min{up,d2−d1}is sent along the shortest path pin subgraph G−Afix. As demand d2−d1needs to be sent in subgraph G−Afix 123 Annals of Operations Research (2022) 312:691–722 713 in any case, and A(p)⊆Afree holds, the resulting robust flow is still feasible, satisfies the desired property (8), and its cost is not increased. Based on the derived knowledge by the presented lemmas, we can finally present an algorithm that solves the RobMCF≡problem on networks based on SP digraphs with a unique source and a unique sink. Algorithm 5.1 Input: SP digraph G=(V,A=Afix ∪Afree), instance I=(G,u,c,b), demand d Output: Robust minimum cost b-flow f Method: 1: Compute a minimum cost flow fthat sends demand d2−d1in subgraph G−Afix with respect to capacity uand cost c 2: Let ube the capacity which results from reducing the capacity uof all arcs of digraph Gthat are used by flow f. By means of the Greedy Algorithm of Bein et al. (1985) compute a minimum cost flow f that sends demand d1in digraph Gwith respect to capacity uand cost c, i.e., flow is sent along shortest paths that still have positive bottleneck values 3: Set f1:= f and f2:= f+f 4: return b-flow f=(f1,f2) Basically, Algorithm 5.1 computes a flow by sending the excess demand in subgraph G−Afix first, and subsequently, by sending the demand through digraph Gwhich is sent in both scenarios. Composing the computed flows to a robust flow leads to an optimal solution obtained in polynomial time as the following theorem shows. Theorem 5 Let G be an SP digraph, and let I=(G,u,c,b)be a corresponding RobMCF≡ instance with demand d=(d1,d2),d 2≥d1. Algorithm 5.1 computes an optimal robust b-flow for demand din polynomial time. Proof We prove the statement by induction on the excess demand, i.e., k:= d2−d1≥0. For the beginning, we consider the case where k=0 holds. As the excess demand is zero, the same amount of flow needs to be sent in both scenarios. Thus, sending the excess demand in subgraph G−Afix in step 1 is omitted. In step 2, a minimum cost flow that sends demand d1through digraph Gis computed by the Greedy Algorithm of Bein et al. (1985). A feasible robust flow results whose scenario flows are equal. The robust flow is optimal by the correctness of the Greedy Algorithm of Bein et al. For the induction step, let ˜ f=(˜ f1,˜ f2)be an optimal robust b-flow for instance Iwhich satisfies without loss of generality the properties of Lemmas 7–11, i.e., in particular, ˜ f2(a)≥ u:= min{up,k+1}for a∈A(p). We consider the RobMCF≡instance  I:= (G,ˆu,c,ˆ b) with the adjusted capacity ˆuand balances ˆ b:= (b1,ˆ b2). Capacity ˆuis obtained by reducing the capacity uof all arcs of path pby u, and accordingly updating the last scenario balances b2of the source and sink results in the new balances ˆ b:= (b1,ˆ b2). Further, we obtain the new demand ˆ d=(d1,ˆ d2)with ˆ d2:= d2−u. As the excess demand is less or equal to kin instance  I, by induction hypothesis Algorithm 5.1 computes an optimal robust ˆ b-flow ˆ f=(ˆ f1,ˆ f2)that sends demand ˆ d=(d1,ˆ d2). We note that robust flow ˆ falso satisfies the properties of Lemmas 7–11. In summary, we obtain that ˆ f2is a flow sending demand ˆ d2=d2−ufor instance  I, and by assumption, ˜ f2is an optimal last scenario flow sending demand d2for instance I. Furthermore, by assumption flow ˜ f2sends udemand along the 123 714 Annals of Operations Research (2022) 312:691–722 shortest path pin subgraph G−Afix. Overall, we obtain for the cost of flow ˆ f2the following upper bound c(ˆ f2)≤c(˜ f2)−u·c(p). By reformulating, we obtain c(ˆ f2)+u·c(p)≤c(˜ f2), and together with the condition that the cost of both flows are determined by the last scenario flows, the following holds true c(ˆ f)+u·c(p)≤c(˜ f). Consequently, flow f=(f1,f2)with scenario flows f1:= ˆ f1and f2:= ˆ f2+fis an optimal robust b-flow sending demand dwhere flow fis defined by f(a):= ufor all arcs a∈A(p). Moreover, flow f=(f1,f2)complies with the flow computed by the Algorithm 5.1 for instance I. Finally, considering the algorithm’s runtime, we compute a minimum cost flow that sends demand d2−d1by the Minimum Mean Cycle-Cancel Algorithm in O(|A|3|V|2log |V|) time (Korte et al. 2012). Subsequently, we compute a flow that sends demand d1by the Greedy Algorithm of Bein et al. (1985)inO(|A|·|V|+|A|log |A|)time. In total, computing a robust minimum cost b-flow takes O(|A|3|V|2log |V|+|A|·|V|+|A|log |A|)time. Note that we cannot use the Greedy Algorithm of Bein et al. (1985) in the first step of Algorithm 5.1 as G−Afix might not be an SP digraph. 6 Conclusion In this paper, we introduced the RobMCF≡problem which is an extension of the MCF problem considering equal flow requirements and demand uncertainty. We presented structural results which differentiate from well known results of the MCF problem. In particular, we showed that Dantzig and Fulkerson’s Integral Flow Theorem (Korte et al. 2012) does not hold anymore. Furthermore, we proved that finding a feasible solution to the RobMCF≡problem is strongly NP-complete on acyclic digraphs, even if a network with a unique source, a unique sink, and unit arc capacities are considered for two scenarios only. On SP digraphs, we proved that the decision version of the RobMCF≡problem is weakly NP-complete. For the special case in which the number of scenarios is not part of the input, we proposed a pseudo-polynomial DP. For the special case of networks based on SP digraphs with a unique source and a unique sink, we provided an algorithm running in polynomial time. For future work, we will study the complexity of the RobMCF≡problem on SP digraphs if the number of scenarios is part of the input. Furthermore, we will study the RobMCF≡ problem for further graph classes as digraphs with bounded treewidth. 123 Annals of Operations Research (2022) 312:691–722 721 causes cost of ten while flow f2does not cause any cost. Since the overall aim is to construct a robust b-flow with minimum cost, flow f1sends the flow unit via the second parallel arc of multi-arc (v3,t)in subgraph G2causing zero cost. Flow f2also sends one flow unit via this arc, and additionally one flow unit via the first parallel arc of multi-arc (v3,t)causing cost of 15. In total, we obtain cost of c(f)=max c(f1), c(f2)=max {10 +0,0+15}=15 =c(f2). Due to the construction of digraph G, sending flow along paths from source sto sink t requires the usage of vertex v3which connects the subgraphs G1and G2. For this reason, we consider in the next step the RobMCF≡problem on the subgraphs G1and G2separately. Therefore, let I1=(G1,u,c,˜ b)be the RobMCF≡instance restricted to subgraph G1with newly defined balances by ˜ b(v) =b(v) for all v∈V(G1)\{v3}, b(t)for v=v3. An optimal solution ˜ f=(˜ f1,˜ f2)to instance I1is equal to solution frestricted to subgraph G1, and causes cost of c(˜ f)=max{c(˜ f1), c(˜ f2)}=max{10,0}=10. Further, let I2=(G2,u,c,ˆ b)be the RobMCF≡instance restricted to subgraph G2with balances ˆ b(v3)=b(s)and ˆ b(t)=b(t). An optimal solution ˆ f=(ˆ f1,ˆ f2)to instance I2 is determined as follows. Both scenario flows ˆ f1and ˆ f2send one flow unit along the third parallel arc of multi-arc (v3,t)while the second scenario flow ˆ f2additionally sends one flow unit along the second parallel arc. This ends up in cost of c(ˆ f)=max c(ˆ f1), c(ˆ f2)=max {10,10 +0}=10. Consequently, the optimal solution ˆ fin subgraph G2causes less cost than the optimal solution fin digraph Grestricted to subgraph G2which causes cost of 15. Conversely, the solution, which results if optimal solutions ˜ fand ˆ fto instances I1and I2 are composed, is feasible but not optimal for instance I. References Ahuja, R.K., Magnanti,T.L.,& Orlin,J.B. (1988). Network flows. Ahuja, R. K., Orlin, J. B., Sechi, G. M., & Zuddas, P. (1999). Algorithms for the simple equal flow problem. Management Science, 45(10), 1440–1455. Ali, A. I., Kennington, J., & Shetty, B. (1988). The equal flow problem. European Journal of Operational Research, 36(1), 107–115. Altin, A., Amaldi, E., Belotti, P., & Pinar, M. Ç. (2007). Provisioning virtual private networks under traffic uncertainty. Networks, 49(1), 100–155. Altin, A., Yaman, H., & Pinar, M. (2011). The robust network loading problem under hose demand uncertainty: formulation, polyhedral analysis, and computations. INFORMS Journal on Computing, 23(1), 75–89. Álvarez-Miranda, E., Cacchiani, V., Dorneth, T., Jünger, M., Liers, F., Lodi, A., Parriani, T., & Schmidt, D.R. (2012). Models and algorithms for robust network design with several traffic scenarios. In A. Ridha Mahjoub, V. Markakis, I. Milis, V.T. Paschos (Eds), ISCO 2012, revised selected papers (vol 7422, pp. 261–272), Atamtürk, A., & Zhang, M. (2007). Two-stage robust network flow and design under demand uncertainty. Operations Research, 55(4), 662–673. 123 722 Annals of Operations Research (2022) 312:691–722 Bein, W. W., Brucker, P., & Tamir, A. (1985). Minimum cost flow algorithms for series-parallel networks. Discrete Applied Mathematics, 10(2), 117–124. Belotti, P., Capone, A., Carello, G., & Malucelli, F. (2008). Multi-layer mpls network design: the impact of statistical multiplexing. Computer Networks, 52(6), 1291–1307. Berman, P., Karpinski, M., & Scott, A. (2004). Approximation hardness of short symmetric instances of max-3sat. Technical report Bertsimas, D., & Sim, M. (2003). Robust Discrete Optimization and Network Flows, 98(1), 49–71. Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. Cacchiani, V., Jünger, M., Liers, F., Lodi, A., & Schmidt, D. R. (2016). Single-commodity robust network design with finite and hose demand sets. Mathematical Programming, 157(1), 297–342. Calvete, H. I. (2003). Network simplex algorithm for the general equal flow problem. European Journal of Operational Research, 150(3), 585–600. Carraresi, P., & Gallo, G. (1984). Network models for vehicle and crew scheduling. European Journal of Operational Research, 16(2), 139–151. Even, S., Itai, A., Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. In 16th annual symposium on foundations of computer science (sfcs 1975) (pp. 184–193). IEEE. Johnson, D.S., & Garey, M.R. (1979) Computers and intractability: A guide to the theory of NP-completeness. WH Freeman. Korte, B., Vygen, J., Korte, B., & Vygen, J. (2012). Combinatorial optimization (Vol. 2). Berlin: Springer. Koster, A.M.C.A.,Kutschka,M.,&Raack,C. (2013).Robustnetworkdesign:formulations,validinequalities, and computations. Networks, 61(2), 128–149. https://doi.org/10.1002/net.21497. Krumke, S. O., & Thielen, C. (2011). Minimum cost flows with minimum quantities. Information Processing Letters, 111(11), 533–537. LenstraJr, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538–548. Manca, A., Sechi, G. M., & Zuddas, P. (2010). Water supply network optimisation using equal flow algorithms. Water Resources Management, 24(13), 3665–3678. Mattia, S. (2013). The robust network loading problem with dynamic routing. Computational Optimization and Applications, 54, 619–643. Meyers, C. A., & Schulz, A. S. (2009). Integer equal flows. Operations Research Letters, 37(4), 245–249. Minoux, M. (1989). Networks synthesis and optimum network design problems: models, solution methods and applications. Networks, 19(3), 313–360. Morrison, D. R., Sauppe, J. J., & Jacobson, S. H. (2013). A network simplex algorithm for the equal flow problem on a generalized network. INFORMS Journal on Computing, 25(1), 2–12. Ohst, J.P. (2016). On the construction of optimal paths from flows and the analysis of evacuation scenarios. Pferschy, U., & Schauer, J. (2013). The maximum flow problem with disjunctive constraints. Journal of Combinatorial Optimization, 26(1), 109–119. Poss, M., & Raack, C. (2013). Affine recourse for the robust network design problem: between static and dynamic routing. Networks,61(2) Sahni, S. (1974). Computationally related problems. SIAM Journal on Computing, 3(4), 262–279. Sanità, L. (2009). Robust Network Design. PhD thesis, Università La Sapienza, Roma. Seedig,H.G.(2009).Networkflowoptimizationwithminimumquantities.InOperations research proceedings 2010 pp. 295–300. Springer. Srinathan, K., Goundan, P.R., Kumar, M.V., Nandakumar, R.,& Rangan, C.P. (2002). Theory of equal-flows in networks. In O.H. Ibarra, L. Zhang, (Eds), Computing and combinatorics (pp. 514–524), Berlin, Heidelberg, Springer Berlin Heidelberg. ISBN 978-3-540-45655-1. Valdes,J., Tarjan,R.E., & Lawler, E.L. (1979). The recognition of series parallel digraphs. In Proceedings of the eleventh annual ACM symposium on theory of computing, STOC ’79 (pp. 1–12) New York, NY, USA, ACM. https://doi.org/10.1145/800135.804393. Valdes, J., Tarjan, R. E., & Lawler, E. L. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2), 298–313. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123