PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Delay-Constrained Maximum Concurrent Flow Problem

Walid Ben-Ameur, Guillaume Beraud-Sudreau, Hervé Kerivin, Sebastien Martin

arXiv:2609.05068v1cs.NImath.OC

TL;DR

The Delay-Constrained Maximum Concurrent Flow problem seeks to maximize throughput subject to path-specific delay bounds. The paper introduces a convex relaxation and proves strong NP-hardness, even for instances with at most three commodities sharing a source and sink.

  • Problem

    DCMCF asks how to maximize the throughput factor while meeting path-specific delay bounds under a load-dependent queuing model.

    Source: §1 · p. 3

  • Method

    The paper introduces a convex relaxation for DCMCF to address the nonconvexity of its delay constraints.

    Source: §1 · p. 4, §1.2 · p. 7

  • Results

    DCMCF's decision problem is strongly NP-hard even with at most three commodities sharing a source and sink.

    Source: §2 · p. 8

  • Takeaways & Limitations

    The paper's treatment of DCMCF includes both complexity analysis and a novel convex relaxation.

    Source: §1.2 · p. 7, §2 · p. 8

    In the formulation discussed, the resulting constraint is not convex.

    Source: §1 · p. 4

Abstract

from arXiv · show

Real-time services, such as VoIP and large-scale neural network training, require strict transmission delay guarantees. While routing under hop constraints is tractable, real-world delays increase sharply with equipment load, typically modeled using the M/M/1 queuing function where delay is inversely proportional to available bandwidth. We investigate the resulting Delay-Constrained Maximum Concurrent Flow (DCMCF) problem, which seeks to maximize the minimum throughput across all commodities. The problem's complexity stems from the conditional and non-linear nature of the delay constraints, which are active only along the specific paths used by the flow. We prove that DCMCF is strongly NP-hard, even for single-source/single-destination instances. To address the inherent non-convexity of the problem, we introduce a new convex relaxation expressed through second-order cone constraints, obtained from the convex envelope of a function representing the conditional delay associated with a single arc of a given path. The relaxation is shown to outperform existing formulations based on disjunctive programming. Leveraging this result, we develop a polynomial-time approximation algorithm with a provable performance guarantee and present numerical experiments demonstrating the effectiveness of the proposed approach.

1 Introduction

The introduction frames DCMCF as maximizing shared throughput subject to path-delay constraints, motivated by the need for predictable latency. It outlines the paper’s contributions on DCMCF hardness, a convex-envelope relaxation, heuristics, and numerical evaluation.

1 Introduction

  • The queuing-model arc delay depends on load, and incorporating path usage into the delay constraint yields a nonconvex constraint.The reformulation accounts analytically for whether a path is used, but is not convex.Source: §1 · pp. 3–4
  • DCMCF maximizes the throughput factor—the largest common proportion of commodity volumes carried—subject to capacity and delay constraints on used paths.The path-delay constraint is active only when the corresponding path carries positive flow.Source: §1 · p. 3

Maximum concurrent flow

  • Without delay constraints, the problem is known to give rise to challenging computational problems; approximation algorithms have been designed, and decomposition methods aim to improve computational efficiency.Source: Maximum concurrent flow · p. 4

Flows with delay considerations

On convex envelopes

  • The authors propose a more direct derivation of the convex envelope, with simple, self-contained proofs.Source: On convex envelopes · p. 7

1.2 Contributions and paper organization

  • The DCMCF problem is strongly NP-hard even with three commodities sharing a source and destination and allowed to use all paths.The paper analyzes the problem’s computational complexity in Section 2.Source: §1.2 · p. 7
  • The new delay-constraint relaxation uses second-order cone constraints from the convex envelope of x/(1 −y) and outperforms the disjunctive programming approach in.The paper introduces the relaxation in Section 3 and compares it with the approach in Section 4.Source: §1.2 · p. 7
  • The paper shows that convex over-estimator heuristics are essentially equivalent to selecting paths explicitly and optimizing convexly over their flow variables.It also proposes several heuristics, including one derived from the new relaxation, and establishes provable performance guarantees for that heuristic.Source: §1.2 · p. 7
  • The paper reports numerical experiments comparing the performance of different relaxations and heuristics.Source: §1.2 · p. 7

2 Complexity

This section analyzes DCMCF’s complexity through a strong NP-hardness reduction and characterizes arc loads, delays, and path-use restrictions among commodities.

2 Complexity

  • DCMCF’s decision problem is strongly NP-hard even with at most three commodities sharing a source and sink and all possible paths available.Source: §2 · p. 8
  • This work provides a stronger characterization than existing results; prior work proved the problem weakly NP-hard using a reduction from a 2-partition problem.Source: §2 · p. 8
  • The reduction maps a 3-Partition instance so that a feasible partition yields a feasible DCMCF solution, while any solution with γ ≥ 1 implies a feasible partition.Source: §2 · pp. 8, 10, 11
  • Commodity kH occupies partition arcs unused by kL, creating high delays that force kL’s routing to encode a partition of the objects.Source: §2 · p. 10
  • The delay-calibration commodity k2 is forced onto 2-hop bypass paths and maintains load exactly 1 on each path.Source: §2 · p. 10
  • Lemma 2.5 states that delays on (s, ui), (vj, t), (vN..., t), and bypass arcs equal 1 for every i and j.The supplied passage says loads on these arcs are also specified, but does not include their values.Source: §2 · p. 13
  • Commodity k2 routes one unit of load through each path in the specified set when its delay is satisfied, saturating those paths and preventing kL or kH from using them.This follows from Equations (10) and Lemma 2.5.Source: §2 · p. 13
  • Lemma 2.7 states that commodity kL has an exact load on each arc (vj, t), although the value is truncated in the supplied passage.The passage begins the value with “W” but does not provide the complete expression.Source: §2 · p. 14
  • Lemma 2.8 gives a load for commodity kH on a family of arcs and states that the delay on each is 1; the arc family and load are truncated here.The supplied text does not preserve the complete arc set or load expression.Source: §2 · p. 14

Appendix A.8. · Appendix A.11.

The appendices establish the 3-Partition reduction’s key flow properties and use them to prove that DCMCF is strongly NP-hard under restrictive commodity and path conditions.

Appendix A.8.

  • For every i ∈ I, commodity kL uses a single arc exiting ui, carrying exactly wi units of that commodity.Source: Appendix A.8 · p. 14
  • For every j ∈ J, commodity kL is carried by exactly three arcs entering the corresponding vertex.Source: Appendix A.8 · p. 14
  • A feasible DCMCF solution of value γ = 1 implies that the corresponding 3-Partition instance is feasible.Source: Appendix A.8 · p. 15
  • The arcs crossed by kL define triplets of objects, and flow conservation with Equation (8) shows each triplet’s weights sum to W.Source: Appendix A.8 · p. 15

Appendix A.11.

  • DCMCF is strongly NP-hard even with at most three commodities sharing a source and destination, when every source-to-destination path can be used by each commodity.Source: Appendix A.11 · p. 15
  • The hardness result holds even when all commodities share one source and destination and every path between them is potentially usable by each commodity.Source: Appendix A.11 · p. 15

3 Relaxation of the delay constraints · 4 Alternative formulations of the DCMCF problem

These sections develop a second-order cone relaxation of the delay constraints using convex under-estimators combined into a convex envelope, and compare it with a disjunctive-programming relaxation. They also describe variable-domain tightening, a Big-M formulation, and additional valid constraints.

3 Relaxation of the delay constraints

  • The delay constraint reduces to studying a non-convex function for each arc, whose convex envelope can be built from regional under-estimators.Source: §3 · p. 15

3.1 Convex envelope of f on Rϵ,θ,η

  • On Rϵ,θ,η, rη is a convex under-estimator on the full domain and equals f’s convex envelope when restricted to that region.Source: §3.1 · p. 17

3.2 Convex envelope of f on Sϵ,θ,η,ζ

  • On Sϵ,θ,ζ,η, sϵ,θ is a convex under-estimator on the full domain and the exact regional convex envelope; its constraint has a second-order cone representation.Source: §3.2 · pp. 18–19

3.3 Convex envelope of f on Tϵ,θ,ζ

  • On Tϵ,θ,ζ, tϵ,ζ is a convex under-estimator on the full domain and equals f’s convex envelope on that region.The associated inequality is a convex hyperbolic constraint.Source: §3.3 · pp. 19–20

3.4 Convex envelope of f on Xϵ,θ,ζ,η

  • On Xϵ,θ,ζ,η, f’s convex envelope is the pointwise maximum of the three regional under-estimators.Figure 3 illustrates the difference between f and its under-estimators and highlights the relaxation’s tightness.Source: §3.4 · pp. 20–21
  • The envelope relaxation is tighter when x is large or y − x is small, corresponding to high path use and low use by other paths.Source: §3.4 · p. 21
  • The convex-envelope constraint can be formulated with second-order cone constraints, making the resulting DCMCFenv relaxation a second-order cone program.Source: §3.4 · p. 21, §3.5 · p. 23

3.6 Computation of a tight domain

  • Tighter variable-domain bounds for DCMCFenv can be computed from arc-load limits induced by delay-constrained paths and by optimizing over a feasible DCMCF solution.The formulation uses lower and upper bounds on arc loads and path-flow variables.Source: §3.6 · pp. 23–24

4.1 A Big-M formulation

  • The Big-M formulation uses binary variables to indicate path use, but its relaxation strength depends strongly on the maximum-delay bounds.The formulation also permits branch-and-bound implementation with commercial solvers and can incorporate the Section 3.5 relaxation.Source: §4.1 · pp. 24–25

4.2 A disjunctive-programming-based relaxation

  • DCMCFenv dominates the disjunctive relaxation DCMCFred and provides tighter bounds than the relaxation proposed in.The authors identify DCMCFred as the strongest relaxation among those proposed in.Source: §4.2 · pp. 25–26

4.3 Additional valid constraints

  • Weighting the delay constraints by commodity size and aggregating them yields additional valid constraints, but numerical tests found no significant impact on problem resolution.Source: §4.3 · pp. 26–27

5 Lower bound heuristics and performance guarantees

The section develops lower-bound heuristics for DCMCF and examines how convex restrictions of conditional constraints reduce to enforcing a constraint or deactivating its trigger. It combines load bounds with a relaxation-based feasible-solution construction to establish polynomial-time approximation guarantees, including guarantees for Hthreshold.

5.1 A negative results on heuristics

  • Any convex restriction of a conditional constraint either enforces its inequality or forces the trigger variable to zero, leaving no intermediate option.Thus, heuristic design must select active constraints; once selected, the resulting problem is convex when the original problem has a convex objective and convex conditional constraints.Source: §5.1 · p. 28

5.2 Active subset heuristics

  • Active-subset heuristics select paths for each commodity, set path variables to zero outside those subsets, and solve the resulting convex problem.The main difficulty is guessing which subsets to select.Source: §5.2 · p. 30

5.2.1 All paths heuristic

  • Selecting all paths for every commodity yields a feasible solution with a strictly positive objective value, called Hall paths.Source: §5.2.1 · p. 30

5.2.2 Greedy heuristic

  • Hgreedy starts with all paths and repeatedly removes a path with a positive p value while the objective increases.Source: §5.2.2 · p. 30

5.2.3 Heuristic based on the DCMCFenv Relaxation

  • Hthreshold uses the DCMCFenv relaxation solution to select path subsets and provides a strictly positive lower bound when its stated threshold condition holds for every commodity.The section also introduces a polynomially encoded lower bound on the optimal objective, described as generally rather loose, for analyzing Hthreshold.Source: §5.2.3 · pp. 30–31

5.3 Performance guarantees of Hthreshold

  • With an appropriately chosen threshold, Hthreshold is an approximation algorithm with provable performance guarantees.The shrinking factor λ transforms a feasible DCMCFenv solution into a feasible DCMCF solution.Source: §5.3 · pp. 31–32
  • Lemma 5.3 gives a uniform shrinking factor for paths with arc-load bounds ua≥b_kγS|P_k|, for γ>0 and S>1.The factor is obtained using the demand sizes, path counts, and arc-load bounds.Source: §5.3 · p. 32
  • Proposition 5.2 guarantees a feasible DCMCF solution from a DCMCFenv solution with objective value ˜γ.The construction removes path usages below threshold S* and scales the remaining flows by the uniform factor from Lemma 5.3.Source: §5.3 · pp. 32–33
  • Lemma 5.4 constructs in polynomial time a DCMCFenv relaxation with arc-load bounds ua≤α(∑_{k∈K} b_k)γ*, for α>1.An iterative process solves the relaxation until the bound criterion is met; these tight bounds combine with Proposition 5.2’s guarantee.Source: §5.3 · p. 33
  • Theorem 5.2 gives a polynomial-time 1/[αβ|K|(|P|−1)+1]-approximation for DCMCF, where α>1 and β=max_{k∈K} b_k.The theorem consolidates the preceding bounds into the algorithm’s final approximation factor.Source: §5.3 · p. 33

6 Numerical experiments … A.3 Proof of Lemma 2.3

This section reports numerical comparisons of heuristics and formulations on SND-Lib and random instances, and concludes with open questions about complexity, relaxations, and approximation. Its appendix proofs use delay bounds to restrict feasible path loads and characterize conditional delay constraints, including the cases in Lemma 2.3.

6 Numerical experiments

  • Tests used SCIP 10.0 on 16 CPUs and 64 GB of RAM, with SND-Lib instances and 126 random instances spanning 25–200 commodities, 10–50 vertices, and 30–475 arcs.The random instances were connected Erdös–Rényi graphs modeled as symmetric directed graphs.Source: §6 · pp. 33–34

6.1 Heuristics

  • Hgreedy dominates Hall paths and tends to perform better on smaller instances, while Hthreshold appears more efficient as the commodity count grows.The heuristic comparison reports gaps relative to the DCMCFenv relaxation.Source: §6.1 · p. 35, Figure 5 · p. 35

6.2 DCMCF relaxations

  • CONVEX dominates S and T, while S yields tighter upper bounds than T on 123 of 126 randomly generated instances.The absence of domination between S and T matches their underlying functions dominating each other on different subsets of the feasible region.Source: §6.2 · p. 36

6.3 DCMCF exact solving

  • On SND-Lib, CONVEX outperformed BIG-M in 11 of 19 instances by gap after one hour or solving time when optimality was reached before the time limit; BIG-M was more efficient on 77 of 126 randomly generated instances.Source: §6.3 · p. 37
  • S and T beat BIG-M on 12 and 13 SND-Lib instances and 72 and 64 random instances, respectively; S beat T on 8 of 19 and 72 of 126.The S and T formulations trade tighter relaxations for solving time.Source: §6.3 · p. 37

7 Conclusion

  • The problem is strongly NP-hard even with three commodities sharing a source and destination, each allowed to use every possible path.The conclusion states the result for this restricted case.Source: §7 · p. 37
  • The paper introduces a relaxation of conditional delay constraints that dominates disjunctive-programming relaxations and an approximation algorithm with a provable performance guarantee.Both are presented as contributions in the conclusion.Source: §7 · p. 38
  • The exact complexity of the single-commodity problem remains unknown; future work could improve relaxations to develop tractable methods for larger instances, or pursue approximation algorithms with improved performance guarantees or refined analysis.Source: §7 · pp. 38–39

A.1 Proof of Lemma 2.1

  • The proof rules out paths for commodity k2 when their zero-load delay already exceeds its delay bound of 2.In particular, the middle arc’s delay strictly exceeds 2, so any path containing it is infeasible for k2.Source: §A.1 · p. 40

A.2 Proof of Lemma 2.2

  • Because k2 sends n + 2m over its feasible paths, the proof rules out any path load above 1 + δ by showing it would exceed d2 = 2.If one feasible path were unused, the average load over the remaining paths would exceed 1 + δ, so at least one path would violate the delay limit.Source: §A.2 · pp. 40–42

A.3 Proof of Lemma 2.3

  • Lemma 2.3’s proof distinguishes arc (ui, t) delay by whether ϵi is zero: it is exactly 1 when zero and greater than 1 + ϵi otherwise.The argument applies these arc-delay cases to the required path s → ui → t, whose total delay for k2 is bounded by d2 = 2.Source: §A.3 · p. 42

A.4 Proof of Lemma 2.4

Applying a reciprocal-delay inequality to the arcs of each 2-hop path yields conditional delay bounds, which the proof uses with commodity k2’s path-delay limit.

A.4 Proof of Lemma 2.4

  • The proof follows Lemma 2.3 by applying 1/(1−e) ≥ 1+e for e<1, strictly when e≠0, to delays on 2-hop paths.Source: §A.4 · p. 43
  • On s→v_j, the first-arc delay is 1/[2−(1+ε_j)], exceeding 1+ε_j for j∈Q_J and equaling 1 otherwise.Source: §A.4 · p. 43
  • With commodity k2’s path-delay cap d2=2, the strict first-arc bound for j∈Q_J implies y(v_j,t)<W.Source: §A.4 · p. 43

A.5 Proof of Lemma 2.5

The proof bounds loads on arcs leaving s and entering t, then compares their total with the flow required to route all three commodities. Reaching that total forces the arc-load bounds to be tight, making the delay on each analyzed arc exactly 1.

A.5 Proof of Lemma 2.5

  • Lemmas 2.3 and 2.4 and the ϵ-variable definitions provide upper bounds on loads along the 2-hop paths.For i ∈ I, the stated bounds are y(s,ui) ≤ mwi + (m −1)W + 1 −ϵi and y(ui,t) ≤1 + ϵi; for j ∈ J, y(s,vj) ≤1 + ϵj and y(vj,t) ≤W.Source: §A.5 · p. 44
  • Because no other arcs leave s or enter t, summing the analyzed arc loads gives a global bound on flow entering and leaving the network.This aggregate bound is compared with the total required to route all three commodities.Source: §A.5 · p. 44
  • Routing the complete demands for all three commodities requires total flow of exactly 2(bL + bH + b2) leaving s and entering t.The proof uses this total to compare required flow with the aggregate upper bounds on the boundary arcs.Source: §A.5 · p. 45
  • Routing the complete demands forces all upper bounds on the arc loads to hold as equalities, so the delay on each analyzed arc is exactly 1.The proof concludes this from the exact required total flow and the aggregate load bounds.Source: §A.5 · p. 45

A.6 Proof of Lemma 2.6

The proof narrows the feasible paths for kL by excluding paths that use specified arcs or exceed its delay limit.

A.6 Proof of Lemma 2.6

  • kL cannot cross arcs of the forms (u_i,t) for i in I or (s,v_j) for j in J, ruling out paths that use those arcs.The proof consequently excludes paths in the stated family beginning with s → u_i → t and a second, partially specified family.Source: §A.6 · p. 45
  • Paths in the remaining considered family have delay strictly greater than dL = 2 + 1/(2W), exceeding kL’s delay limit.The proof concludes that only the other remaining paths can be feasible for kL; their family is truncated in the supplied passage.Source: §A.6 · p. 45

A.7 Proof of Lemma 2.7 · A.8 Proof of Lemma 2.8

The proofs establish the routed-flow structure for commodities kL and kH, then use flow conservation and delay functions to verify the corresponding demand and unit-delay conclusions.

A.7 Proof of Lemma 2.7

  • The proof of Lemma 2.7 uses exclusive entry through arcs {(v_j, t)}_{j∈J} and Equation (8) to establish their total loads.Source: §A.7 · p. 45
  • Because commodity k2 routes 1 unit on each entry arc, the remaining flow on those arcs belongs to commodity kL.Source: §A.7 · p. 45
  • Summing kL’s flow over the m arcs confirms that its total routed volume matches demand bL = W.Source: §A.7 · p. 46

A.8 Proof of Lemma 2.8

  • Equation (9) establishes the total loads on the arcs, and after commodity k2 routes 1 unit on each, the remaining flow belongs to kH.Source: §A.8 · p. 46
  • Flow conservation extends the kH load result to all arcs in the chain because kH must cross the chain to reach its entry arcs.Source: §A.8 · p. 46
  • Substituting the loads into the delay functions confirms that the delay on each of these arcs is exactly 1.Source: §A.8 · p. 46

A.9 Proof of Lemma 2.9 · A.10 Proof of Lemma 2.10

The proofs use delay limits and flow conservation to establish a rigid routing pattern for commodities kL and kH. At each vj, the load balance then forces exactly three incoming arcs to carry kL.

A.9 Proof of Lemma 2.9

  • Delay limits bound each used arc’s load by wi + W for kH and by wi for kL.Source: §A.9 · pp. 46–47
  • Flow conservation requires at least m − 1 outgoing arcs from each ui to carry loads strictly greater than wi.Source: §A.9 · p. 47
  • Commodity kL must use exactly one arc (ui, vj) per object i and route exactly wi units on it, since its demand is W = ∑i wi.Source: §A.9 · p. 47
  • The remaining m − 1 arcs from each ui carry exactly wi + W units of commodity kH.Source: §A.9 · p. 47

A.10 Proof of Lemma 2.10

  • For each vj, if l incoming arcs carry kL, the other n − l carry kH, with respective arc loads wi and wi + W.Source: §A.10 · p. 48
  • Flow conservation at each vj equates the two load expressions and forces l = 3, so exactly three arcs carry kL.Source: §A.10 · p. 48

A.11 Proof of Proposition 2.2 … B.2 Proof of Lemma 5.3

The proofs establish a 3-Partition correspondence and derive monotonicity-based bounds used in the performance-guarantee argument. Together, these steps support the stated partition validity and parameter bounds.

A.11 Proof of Proposition 2.2

  • Each subset Tj contains exactly 3 elements, and because every object i ∈ I is assigned to exactly one subset, the collection {Tj}j∈J forms a partition.Source: §A.11 · pp. 48–49
  • Flow conservation makes the weight sum in each T_j equal W, yielding a valid 3-Partition of the multiset {w_i}.The entering load is ∑_{i∈T_j} w_i and the exiting load is W.Source: §A.11 · p. 49

B.1 Proof of Proposition 5.1

  • For y ∈ ]η, 1 − ϵ], q_{ϵ,θ} increases with x over [0, min(y − θ, 1 − ζ)].The proof establishes this using the derivative of q_{ϵ,θ}.Source: §B.1 · p. 49
  • The derived lower bound is λ_{ϵ,x0} = 4x0(1−ϵ)/(1−ϵ+x0)^2, attained at y* = (1−ϵ+x0)/2.The proof obtains the bound by minimizing q_{ϵ,0}(x0,y) over y.Source: §B.1 · p. 49

B.2 Proof of Lemma 5.3

  • Under ua ≥ b_kγS|P_k|, the bound expression decreases with |P_k|, enabling its lower bound at the corresponding limiting value.The proof first establishes the derivative condition for |P_k| and then applies the assumption.Source: §B.2 · p. 50
  • Under the same assumption, the expression also decreases with ua and is bounded below using u = max_a ua.The proof compares the expression at ua with its value at u.Source: §B.2 · p. 50

B.3 Proof of Proposition 5.2 · B.4 Proof of Lemma 5.4 · B.5 Proof of Theorem 5.2

These proofs establish how a solution to the relaxation yields a feasible DCMCF solution and how a suitable relaxation can be found by iteratively improving bounds. The final proof applies those results to a DCMCF instance.

B.3 Proof of Proposition 5.2

  • From a DCMCFenv solution with S > 1, the proof constructs a DCMCF solution and verifies that it satisfies the required constraints.The construction is shown to be feasible, and its objective value is bounded in terms of the relaxation solution.Source: §B.3 · pp. 50–51
  • The constructed DCMCF solution has an objective value bounded below using the relaxation value and the path-set size.The proof selects S to maximize the lower bound on the constructed solution’s objective.Source: §B.3 · p. 51

B.4 Proof of Lemma 5.4

  • The Lemma 5.4 proof iteratively solves relaxations, stopping on direct success or improving bounds when the desired property is not met.The bounds-improvement case creates and solves a new relaxation while retaining a valid upper bound on each arc’s load.Source: §B.4 · p. 52
  • The iterative process terminates with a relaxation satisfying the required conditions within a polynomially bounded number of iterations.If direct success has not occurred after 1 + |A| iterations, some arc’s upper bound has been updated twice; the proof uses the lower bound γlow to establish termination.Source: §B.4 · p. 52
  • The iteration count is polynomially bounded because it is bounded using the trivial upper bound on total flow.The proof compares the number of iterations with the upper bound ∑a∈A ca ∑k∈K bk.Source: §B.4 · p. 52

B.5 Proof of Theorem 5.2

  • For any constant α > 1, the Theorem 5.2 proof uses Lemma 5.4 to construct a DCMCFenv relaxation with optimal value γ*, then invokes Proposition 5.2.The supplied proof passage ends as it introduces the DCMCF solution guaranteed by Proposition 5.2.Source: §B.5 · pp. 52–53
Loading 2609.05068v1…