Source-linked AI summary
On the Delay-Constrained Maximum Concurrent Flow Problem
Walid Ben-Ameur, Guillaume Beraud-Sudreau, Hervé Kerivin, Sebastien Martin
TL;DR
DCMCF asks how to maximize concurrent throughput while respecting load-dependent, path-conditional transmission delays. The paper proves strong NP-hardness, develops a convex-envelope relaxation for the nonconvex constraints, and derives approximation methods with provable guarantees. Its complexity result already holds for three commodities sharing a source and destination, while the supplied evidence directly supports the nonconvex formulation and reduction result.
Problem
DCMCF seeks maximum concurrent throughput under nonlinear M/M/1 load-dependent delays that apply conditionally to used paths, producing nonconvex constraints.
Method
The paper uses a 3-Partition reduction for complexity and introduces a novel convex relaxation based on convex-envelope analysis of the conditional delay constraints.
Results
DCMCF is strongly NP-hard even with at most three commodities sharing the same source and destination, with every source-to-destination path potentially available.
Takeaways & Limitations
The problem remains computationally hard under highly restricted commodity and terminal structure, motivating relaxation-based approximation methods.
Takeaways & Limitations
The delay reformulation that incorporates path usage is differentiable but nonconvex.
Abstract
from arXiv · showhide
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
DCMCF models maximum concurrent throughput when arc delays depend nonlinearly on load and apply conditionally to used paths. The paper studies its complexity and develops a convex-envelope relaxation for the resulting nonconvex constraints.
- Problem formulation: DCMCF maximizes the throughput factor shared across commodities while enforcing capacity and path-delay limits.The throughput factor γ represents the maximum proportion of each commodity that the network can carry.
- Problem formulation: A path-delay constraint is active only when the corresponding path carries positive flow, creating a conditional nonlinear constraint.The formulation incorporates path usage into a differentiable constraint, but the resulting constraint is not convex.
- Related work: Prior work addresses related delay-constrained flow variants through heuristics, relaxations, decomposition, branch-and-bound, branch-and-price, and local optimization.Existing results include a weak NP-hardness result for a cost version and relaxations based on disjunctive or big-M formulations.
- Contributions: The paper proposes a direct convex-envelope derivation with self-contained proofs, introduces a novel convex relaxation, and develops heuristics with provable performance guarantees.The proposed relaxation is reported to outperform the disjunctive-programming approach in.
2 Complexity
The complexity proof reduces 3-Partition to a three-commodity DCMCF instance sharing one source and destination. Carefully designed delay limits and bypass paths force routing patterns that encode a valid triplet partition.
- Complexity result: Therefore DCMCF is strongly NP-hard even with at most three commodities sharing source and destination and unrestricted commodity path availability.The result strengthens the previously cited weak NP-hardness result for a related cost version.
- Reduction: The reduction starts from 3-Partition, which asks whether weighted objects can be divided into m equal-sum triplets.Here m = n/3 and each triplet must sum to W/m, where W is the total weight.
- Construction: The constructed DCMCF instance has three commodities sharing source s and destination t, with all possible paths available to each commodity.Its network contains object vertices, triplet vertices, chains, partition arcs, completion arcs, and capacity-2 bypass arcs.
- Forced routing: Commodity k2 is forced by its tight delay limit onto specified two-hop bypass paths and uses every such path with a calibrated load.This fixes the loads and delays needed to constrain the other commodities.
- Correctness: If the 3-Partition instance is feasible, the constructed DCMCF instance admits a feasible solution with concurrent throughput γ ≥ 1.The proof routes kL through triplet-assignment paths, kH through complementary partition paths, and k2 through bypass paths.
Appendix A.8.
The appendix establishes that feasible DCMCF routing encodes a 3-Partition solution through the arcs used by the light commodity. It identifies unique object-to-triplet assignments and derives equal triplet weights.
- Object assignments: For each object i, commodity kL uses a single arc leaving vertex ui with load exactly wi.This uniquely associates each object with the triplet vertex reached by that arc.
- Triplet structure: For every triplet vertex vj, commodity kL enters through exactly three arcs.The conclusion follows from the allowable partition-arc loads and flow conservation at vj.
- Complexity consequence: Together with the reduction propositions, these lemmas establish strong NP-hardness under shared-source, shared-destination, three-commodity, unrestricted-path conditions.The theorem derives the complexity result from the two-way reduction between 3-Partition and DCMCF feasibility.
- Partition recovery: The selected kL arcs therefore construct triplets from the original objects, while flow conservation and the governing equation imply each triplet has total weight W/m.This recovers the feasibility condition of the 3-Partition instance.
3 Relaxation of the delay constraints
The section derives convex relaxations for the non-convex delay function by partitioning its domain and computing convex envelopes on each region. These envelopes combine into a second-order cone representable relaxation that dominates disjunctive-programming alternatives.
- Motivation: The difficult DCMCF constraints arise from the non-convex function f(x, y) = x/(1 − y), representing an arc-level delay term.The formulation decomposes additive path-delay terms into separate arc-level functions.
- Domain partition: The domain is partitioned into Rϵ,θ,η, Sϵ,θ,ζ,η, and Tϵ,θ,ζ, with the convex envelope computed separately on each subset.The three regional envelopes are then combined to represent the envelope over the full domain.
- Regional convex envelopes: On Rϵ,θ,η and Sϵ,θ,ζ,η, rη and sϵ,θ are convex under-estimators, with sϵ,θ equal to the convex envelope on Sϵ,θ,ζ,η.Propositions 3.1 and 3.2 establish the under-estimator properties and the exact envelope on the relevant regions.
- Regional convex envelopes: On Tϵ,θ,ζ, tϵ,ζ is a convex under-estimator and equals the convex envelope restricted to Tϵ,θ,ζ.This supplies the third regional component needed for the global envelope.
- Conic formulation: The global envelope is max(rη, sϵ,θ, tϵ,ζ), and imposing its upper bound can be formulated as a second-order cone program.The sϵ,θ component is itself expressible through hyperbolic and linear constraints, enabling the conic formulation.
- Comparison: The resulting DCMCFenv formulation provides tighter bounds than the disjunctive-programming-based relaxation and dominates DCMCFred.The comparison is reported as a formulation-level strengthening rather than as a numerical performance metric.
5 Lower bound heuristics and performance guarantees
The section shows that convex restrictions of conditional constraints reduce to discrete active/inactive choices, motivating path-subset heuristics. It then develops threshold-based selection and derives polynomial-time approximation guarantees.
- Negative result on heuristics: Conditional constraints admit no intermediate convex restriction: each must be enforced or its trigger variable fixed to zero.This follows from the theorem characterizing convex subsets of the conditional feasible region.
- Negative result on heuristics: Convex-restriction heuristics therefore select active constraints, solve the resulting convex problem, and face difficulty in choosing the active subset.For DCMCF, the heuristic selects path subsets Qk and sets path-flow variables to zero outside them.
- Active subset heuristics: The Hall paths heuristic retains all paths and solves the resulting convex DCMCFsubset problem to obtain a feasible solution with strictly positive objective value.A greedy variant repeatedly removes a path when doing so increases the objective.
- Threshold heuristic: Hthreshold selects paths using a threshold on the convex relaxation solution and provides a strictly positive lower bound for DCMCF.The bound is polynomially encoded, although it is generally rather loose.
6 Numerical experiments
The experiments compare heuristics and four relaxations on SND-Lib and randomly generated instances, showing that tighter relaxations can trade off against solving time. CONVEX dominates S and T theoretically, while BIG-M, S, and T can be more effective computationally depending on the instance set.
- Experimental setup: The experiments use SND-Lib instances and 126 randomly generated instances spanning 25–200 commodities, 10–50 vertices, and 30–475 arcs.The formulations were implemented in SCIP 10.0 and tested on a machine with 16 CPUs and 64 GB of RAM.
- Heuristics: Hgreedy dominates Hall paths and tends to perform better on smaller instances, whereas Hthreshold appears more effective as the number of commodities increases.The heuristic comparisons use gaps relative to the DCMCFenv relaxation, identified as the tightest known relaxation for the delay-constrained problem.
- Relaxation bounds: CONVEX necessarily has a tighter upper bound than S and T because it contains all constraints from both relaxations.The reported comparisons measure relative gains against BIG-M using the objective values of the relaxations and heuristic lower bounds.
- Relaxation bounds: S provides tighter upper bounds than T on 123 of 126 randomly generated instances, although S and T do not dominate one another in general.The paper attributes this general non-domination to the different feasible-region subsets where the functions sϵ,γ and tϵ,ζ dominate each other.
- Exact resolution: CONVEX outperformed BIG-M on 11 of 19 SND-Lib instances, while BIG-M was more efficient on 77 of 126 randomly generated instances.CONVEX is tighter but takes longer to solve, so its computational advantage depends on the instance family.
- Exact resolution: S and T offer trade-offs between relaxation tightness and solution time, outperforming both BIG-M and CONVEX on different subsets of instances.They outperform BIG-M on 12 and 13 SND-Lib instances and on 72 and 64 randomly generated instances, respectively; S is more efficient than T on 8 of 19 SND-Lib and 72 of 126 random instances.
A.4 Proof of Lemma 2.4
The proof analyzes each two-arc path s → v_j → t under the maximum delay bound, distinguishing j ∈ Q_J from other indices. It derives load and delay implications for both arcs.
- Applying the inequality 1/(1−ϵ) ≥ 1 + ϵ to the two-arc paths bounds their aggregate delays.The inequality is valid for ϵ < 1 and is strict when ϵ ≠ 0.
- For j ∈ Q_J, the first arc has delay strictly greater than 1 + ϵ_j, while otherwise its delay equals 1.
- Because commodity k_2 has maximum delay 2, every path s → v_j → t must satisfy d(s,v_j) + d(v_j,t) ≤ 2.
- For j ∈ Q_J, the strict first-arc inequality yields a strict residual constraint on the second-arc delay.
- For j ∉ Q_J, the equality on the first arc similarly yields a corresponding bound on the second-arc delay.
- Enforcing maximum delay 2 across the path guarantees the stated feasibility condition for the two-hop routing.
A.5 Proof of Lemma 2.5
The proof sums arc-load bounds around the source and sink to obtain a global network bound. Routing the complete demands forces these bounds to hold as equalities, fixing the relevant loads and delays.
- Summing the source and sink loads produces a global bound because no other arcs leave s or enter t.
- The proof concludes that successfully routing throughput γ = 1 requires the stated union of index sets.
- The proof bounds loads on every two-hop path by combining Lemmas 2.3 and 2.4 with the definitions of the ϵ variables.
- For each i ∈ I, the outgoing and incoming arc loads satisfy the stated upper bounds involving m w_i, W, and ϵ_i.
- For each j ∈ J, the arc loads satisfy y(s,v_j) ≤ 1 + ϵ_j and y(v_j,t) ≤ W.
- Routing all three complete demands requires total flow 2(b_L + b_H + b_2) across the source and sink cuts.
- All upper bounds therefore hold as strict equalities, and the resulting arcs have delay exactly 1.
A.6 Proof of Lemma 2.6
The proof excludes the high-delay two-hop paths from commodity k_L’s feasible routing options. It therefore restricts k_L to the remaining paths.
- Commodity k_L cannot cross arcs in the specified outgoing and incoming arc sets, excluding the corresponding two-hop paths.
- The excluded paths have delay strictly greater than d_L = 2 + 1/(2W), exceeding k_L’s delay limit.
- Consequently, the only feasible paths for k_L are those in the remaining path family.
A.7 Proof of Lemma 2.7
The proof determines the flow of commodity k_L on the arcs entering t through v_j. Since commodity k_2 already uses one unit on each such arc, the remaining capacity carries k_L and totals its demand.
- Commodity k_L enters t exclusively through the arcs (v_j,t), whose total load is fixed at W/m + 1.
- Summing across the m arcs gives total routed volume b_L = W for commodity k_L.
- The analogous argument fixes the remaining loads on the other entering arcs after accounting for commodity k_2’s unit flow.
- Flow conservation extends the load result through the entire arc chain used by commodity k_H.
- Substituting these loads into the delay functions confirms the stated per-arc delays.
A.9 Proof of Lemma 2.9
The proof establishes structural flow properties for commodities kL and kH, forcing kL to use exactly three arcs per destination node and yielding a 3-Partition solution.
- Flow bounds: At least m −1 arcs leaving each ui carry load strictly greater than wi.Otherwise, the total outgoing flow would be less than mwi + (m −1)W.
- Flow bounds: Commodity kL can cross at most one arc from each object node ui and must route exactly wi units through it.Its demand is bL = W = ∑i∈I wi, so it uses one arc per object node.
- Destination-node structure: For each destination node vj, arcs carrying kL have load wi, while arcs carrying kH have load wi + W.The total load depends on the number l of arcs entering vj that carry kL.
- Destination-node structure: Commodity kL is carried by exactly 3 arcs entering each vj.The proof derives l = 3 from flow conservation and the associated load expressions.
A.11 Proof of Proposition 2.2
The proof derives a lower-bound factor for the convex-envelope relaxation by analyzing monotonicity of its auxiliary function and bounding relevant path and arc parameters.
- Envelope bound: The auxiliary function qϵ,θ is increasing in x over its specified domain for fixed y.This follows from the sign of its derivative.
- Envelope bound: The function qϵ,θ is also increasing in θ under the stated condition.This monotonicity supports replacing parameters with lower-bound values.
- Envelope bound: The minimum of qϵ,0(x0, y) occurs at y∗ = (1−ϵ+x0)/2, with value 4x0(1−ϵ)/(1−ϵ+x0)^2.This value defines λϵ,x0 used in the bound.
- Parameter monotonicity: The bound decreases with path length |Pk| when ua ≥ bkγ/(S|Pk|).The proof uses the derivative with respect to |Pk| and the stated assumption.
- Parameter monotonicity: The bound also decreases with ua under the analogous condition, allowing replacement by the maximum arc parameter u.This yields the final lower-bound expression used in the proposition.
B.3 Proof of Proposition 5.2
The proof constructs a feasible DCMCF solution from a DCMCFenv solution and establishes a lower bound on the recovered objective, while also showing that iterative bound improvement is polynomially bounded.
- Solution construction: A feasible DCMCF solution is constructed from a DCMCFenv solution with objective value ˜γ.The constructed variables satisfy the DCMCF constraints, including constraints (6).
- Approximation bound: Choosing S∗ = 2 − 2|P| + b˜γ/(u|P|) maximizes the lower bound on the recovered objective.The proof restricts the choice to S > 1.
- Approximation bound: The constructed DCMCF solution satisfies ¯γ ≥ b˜γ/[u(|P|−1)+b˜γ].This relates the original objective to the relaxation objective through the path-length and parameter terms.
- Iterative refinement: The relaxation sequence either succeeds directly or improves arc-load upper bounds by solving a new relaxation.Each iteration updates bounds when the desired property is not immediately satisfied.
- Iterative refinement: The iterative process terminates after at most (|A| + 1) iterations and is polynomially bounded in the instance size.Termination follows because the required conditions are reached before an arc can be updated twice without violating the lower bound.