On the Delay-Constrained Maximum
arXiv:2609.05068v1 [cs.NI] 4 Sep 2026
Concurrent Flow Problem Walid Ben-Ameur ([email protected])1 , Guillaume Beraud-Sudreau (corresponding author [email protected])2,3 , Hervé Kerivin ([email protected])3 , and Sebastien Martin ([email protected])2 1 SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris,19 place Marguerite Perey 91120 Palaiseau, France
2 Huawei Technologies Ltd., Paris Research Center, 18 Quai du Point du Jour, 92100 Boulogne-Billancourt, France
3 LIMOS, Université Clermont Auvergne, CNRS, 1 Rue de la Chebarde, 63178 Aubière, France
March 2025
Abstract 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
1
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/singledestination 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
Over the past two decades, the expansion of cloud computing has intensified the demand for predictable end-to-end latency in telecommunications. This requirement is now critical across the spectrum, from consumer-facing applications like gaming and live streaming to large-scale enterprise operations, such as the distributed training of large language models across multiple data centers [9]. This requirement can be approached as a traffic-engineering problem, which is formulated as a multi-commodity flow problem, where the telecommunication network is represented by a directed graph D = (V, A) and end-to-end communications are represented as commodities [33].
The
terms vertex and node are used interchangeably to denote an element of V, whereas arc and link refer to an element of A. An arc a directed from u to v is denoted by (u, v) and has a capacity c a > 0 which could also be denoted c(u,v) . We consider a set K of commodities with, for each commodity k ∈ K, a source sk , a destination (or target) tk and a size (or volume) bk . We also use Pk to denote a given nonempty subset of paths from sk to tk . For p ∈ Pk , x kp is the proportion of the commodity k ∈ K carried through the path p. A given value dk represents the maximum allowed delay for commodity k. The delay through an arc a, denoted by d a , is given by the 2
average delay function d a = 1/(ca −ya ) following from the classical M/M/1 queuing model [20], where y a denotes the flow (or load) of a. Consequently, for any path p ∈ Pk carrying positive flow (i.e., if x kp > 0), the total delay through p should be less than or equal to dk . The Delay-Constrained Maximum Concurrent Flow problem (denoted DCMCF) can then be expressed as follows: DCMCF:
max γ
∑ xkp = γ
∀k ∈ K
(1)
∀a ∈ A
(2)
∀k ∈ K, p ∈ Pk
(3)
ya ≤ ca
∀a ∈ A
(4)
x kp ≥ 0
k
(5)
p∈ Pk
∑
ya ≥
x kp bk
k ∈K,p∈ Pk | a∈ p
1
∑ c a − y a ≤ dk
if x kp > 0
a∈ p
∀k ∈ K, p ∈ P .
Observe that γ represents the throughput factor, or maximum proportion of each commodity that can be carried through the network. Constraints (1) establish the connection between γ and the x kp proportions ; the equality sign used in this formulation could be equivalently replaced by an inequality without changing the optimal solution of this problem. Constraints (2) relate the flow on an arc a ∈ A to the sum of flows on paths containing a. The delay constraints are stated in (3). Observe that each Constraint (3) is active if and only if the corresponding path is used (i.e., if x kp > 0). Constraints (4) introduce capacity limitations; note that, because of the delay constraint, the load of each arc is always strictly lower than its capacity. Observe that the delay along a path p ∈ Pk is at least ∑ a∈ p c1a . We may therefore assume that ∑ a∈ p c1a < dk for each path p ∈ Pk , since any
path violating this condition can be discarded.
After multiplication by x kp , (3) can be reformulated as: x kp
∑ ca − ya ≤ xkp dk
∀k ∈ K, p ∈ Pk .
(6)
a∈ p
It is worth highlighting that, while this reformulation of the delay constraint incorporates the path-usage condition into a differentiable analytical 3
form, the resulting constraint is not convex. We can now introduce some relevant notation for the convexity analysis of functions. Given a bounded real-valued function f defined on a compact nonempty set X , the convex envelope of f over X is the function fˇ : X ∋ x 7→ fˇ( x ) = inf{u : ( x, u) ∈ conv(epi( f ))}, where epi( f ) = {( x, u) : f ( x ) ≤ u} and conv(.) of a set represents its convex hull. In other words, fˇ is the highest convex under-estimator of f over X . If this is not clear from the context, the subscript X can be added to emphasize that we are considering the convex envelope over X , thus leading to the notation fˇX . One can also express fˇ( x ) by considering a convex combination over X representing x and minimizing the combination of f ’s values: fˇX ( x ) = inf ∑ λi f (vi ) λi v ∈X i
∑ λi vi = x,
vi ∈X
1.1
∑ λi = 1, λi ≥ 0.
vi ∈X
Related work
Maximum concurrent flow The maximum concurrent flow problem without delay constraints can be formulated as a linear program and, in principle, solved using standard optimization tools [1]. Nevertheless, even this version—without delay constraints—is known to give rise to challenging computational problems (see, e.g., [6, 7]). This led many researchers to design approximation algorithms for the problem [7, 11, 14, 19, 21, 24]. Furthermore, several decomposition methods are proposed in [2] to improve computational efficiency. In the special case where all commodities share a common source, a strongly polynomial-time combinatorial algorithm is also presented in [2]. Regarding the theoretical significance of the maximum concurrent flow problem, it can be interpreted as the dual of the linear programming relaxation of the sparsest cut problem. A sparsest cut is defined as a cut that minimizes the ratio between the capacity of the cut and the total demand 4
separated by it. Many approximation algorithms for the sparsest cut problem are based on solutions to the maximum concurrent flow problem (see, e.g., [31]). Flows with delay considerations When the delay on each link is constant and identical across all links, incorporating delay constraints is equivalent to imposing a bound on the number of links in the selected path. This can be handled efficiently via dynamic programming, by solving shortest-path problems under hop constraints to generate feasible paths [1, 29]. When the delay on a link is given by 1/(c a − y a ), and the goal is to to minimize the average end-to-end delay of the demands over a network, the resulting objective function is then ∑ a y a /(c a − y a ), which can be minimized within a convex optimization framework. The survey [27] provides a comprehensive overview of solution approaches for convex-cost multicommodity flow problems, in which the objective is to minimize the total cost—defined as the sum of convex arc costs—while satisfying all demand requirements. The average end-to-end delay minimization problem has also been considered with the additional constraint that each flow should be unsplittable. In [34], a near-optimal solution is computed through a Lagrangian relaxation when delay constraints follow Kleinrock functions, while [12] proposes a branch-and-bound approach to solve this problem when average delays are approximated by piecewise-linear functions. A branch-and-price method is described in [5] to solve the problem for convex delay functions. The work of [3], that formalizes delay constraints and provides some heuristic solutions, is one of the earliest and most closely related contributions to the present study. The cost version of the DCMCF problem was further investigated in [4], where its weak NP-hardness was established through a reduction from the 2-Partition problem. In addition, convex relaxations were proposed to effectively handle the delay constraints. A relaxation based on a disjunctive formulation of the delay constraints is 5
proposed in [16] ; more details will be provided in Section 4.2. Furthermore, [15] considers an outer-approximation of a big-M reformulation of the delay constraints. The same authors study in [17] a robust version of the problem, where a random component is added to the delay function. While these works on the delay-constrained multi-commodity flow problem considered a set of paths given as input, in [32], the authors study a branch-and-price approach to solve a more general problem where the paths are built through an arc-node representation of the problem. In another approach, [10] and [28] provide efficient ways to compute locally optimal solutions of the delayconstrained multi-commodity flow problem. Another form of delay constraints, where delays are proportional to link loads, has been considered in [8], where the authors prove the NPcompleteness of the problem and provide polynomial approximations under assumptions on the paths and graph topologies. On convex envelopes The convex relaxation of the delay constraints in Section 3 relates to the extensive literature on convex envelopes and, more generally, on convex under-estimator computations. The best known and probably most widely used convex-estimator is obtained through the McCormick envelopes of the bilinear function xy on a rectangular domain [25]. Several studies investigate the convex envelopes of function classes over special domains. We review here the works that are most closely related to the material presented in Section 3. [30] studies bilinear functions over “D-polytopes" where a Dpolytope is such that all edges have a non-negative slope. Notice that the function studied in Section 3 is not bilinear and the polytope considered there is not a D-polytope. More recently, [23] studied the convex envelope of bivariate functions over polytopes under the assumption that the Hessian matrix is indefinite and that the restriction of the function along each edge is either concave or strictly convex. Their approach relies on solving a convex optimization problem. 6
Another approach proposed by the same author in [22] is based on a polyhedral subdivision of the polytope and on the solution of a number of subproblems that grows exponentially with the number of vertices of the polytope. The special case of fractional functions is also investigated in [22]. Since the function x/(1 − y) considered in Section 3 is fractional and satisfies all the properties mentioned above, the approach of [22] could, in principle, also be used to compute its convex envelope. Nevertheless, we propose a more direct approach to derive the convex envelope, together with simple and self-contained proofs.
1.2
Contributions and paper organization
The remainder of the paper is organized as follows. In Section 2, we analyze the computational complexity of the DCMCF problem and prove that it is strongly NP-hard, even when restricted to three commodities that share a common source and destination and are allowed to use all possible paths. Section 3 introduces a novel convex relaxation of the delay constraints. The resulting formulation is expressed through second-order cone constraints obtained from the convex envelope of the fractional function x/(1 − y). We then show in Section 4 that our formulation outperforms the disjunctive programming approach proposed in [16]. Section 5 is dedicated to theoretical analysis of heuristics for the DCMCF problem. We first show that heuristics based on convex over-estimators are essentially equivalent to explicitly selecting paths and solving a convex optimization problem defined over flow variables associated with those paths. We then propose several heuristics, including one derived from the new convex relaxation, and establish provable performance guarantees for it. Finally, Section 6 reports numerical experiments comparing the performance of the different relaxations and heuristics.
7
2
Complexity
We prove that the decision problem associated with DCMCF is strongly NPhard, even when there are at most three commodities, when all commodities share the same source and the same sink, and when the available path sets Pk include all possible paths for every commodity k ∈ K. This provides a stronger characterization than existing results in the literature. Previous work by [4] proved that the problem is weakly NP-hard, using a reduction from a 2-partition problem with a large number of commodities having distinct sources and destinations. Another form of delay constraints, where delays are proportional to link loads, was considered in [8]. The authors proved the NP-completeness of that variant and provided polynomial approximations under specific assumptions on the paths and graph topologies. We consider a reduction from the 3-Partition problem [13]. This problem is defined as follows: decide whether a set I of n objects with sizes
{wi }i∈ I can be partitioned into m = n/3 disjoint subsets (triplets) { Tj } j∈ J , such that each subset has the same sum W/m, where W = ∑i∈ I wi . To prove the NP-hardness of DCMCF, we build an instance of DCMCF that admits a maximum concurrent flow of value γ ≥ 1 if and only if the given 3-Partition instance is of True type. Since scaling all object weights by the same positive factor does not affect the 3-Partition feasibility, we assume without loss of generality that the total weight is W = (2n1 )2 . We also assume that wi ≤ W/m for each object i ∈ I, as the 3-Partition instance is otherwise trivially infeasible, and that m ≥ 2 (or n ≥ 6) — as the 3-Partition problem involving a single triplet is trivially feasible. Finally, we denote N = (2n)2 . Given such a 3-Partition instance, we construct a DCMCF instance on a directed graph D = (V, A) as illustrated in Figure 1. The set of vertices V consists of the following elements: • A source vertex s and a destination vertex t.
8
𝑢1 𝑤1 + 2W
𝑚𝑤1 + 𝑚 − 1 𝑊 + 2
𝑣1
𝑤1 + 2W
𝑊 𝑛+1 𝑛−3 +1 𝑛
𝑣11 𝑤1 + 2W
𝑊 𝑚
𝑣12 𝑣13
+2
𝑣1𝑁−1
𝑣𝑗 𝑠
𝑢𝑖
𝑊
𝑣𝑗1
𝑣𝑗2
𝑚
𝑣𝑗3
𝑁−1 𝑣𝑚
𝑤𝑛 + 2W
3 𝑣𝑚 1 𝑣𝑚
𝑤𝑛 + 2𝑊
𝑚𝑤𝑛 + 𝑚 − 1 𝑊 + 2
𝑢𝑛
2 𝑣𝑚
𝑊 𝑛+1 𝑛−3 +2 𝑛
𝑣𝑗𝑁−1 𝑣𝑗𝑁
2
2
𝑣1𝑁
+2
𝑊 𝑚
𝑡
𝑁 𝑣𝑚
+2
𝑣𝑚
𝑤𝑛 + 2W
Figure 1: Instance of the DCMCF problem associated with the 3-Partition problem of a set {wi }i∈ I . Only selected arcs, vertices, and capacities are shown. All dashed arcs have a capacity of 2. • Object vertices: a first layer of n vertices {ui }i∈ I , where each vertex corresponds to an object in the 3-Partition instance. • Triplet vertices: a second layer of m = n/3 vertices {v j } j∈ J , where each vertex corresponds to a target triplet j ∈ J. • Chains of vertices: for each j ∈ J, a sequence of vertices {vlj }l ∈{1,...,N } . We will prove that the subpath traversing these vertices is accessible to exactly one commodity, which will force its routing and flow. The set of arcs A contains the following elements (colors refer to Figure 1): • Source-objects arcs (purple): ∀i ∈ I, an arc (s, ui ) with capacity c(s,ui ) = mwi + (m − 1)W + 2. • Partition arcs (blue): ∀i ∈ I, j ∈ J, an arc (ui , v j ) with capacity c(ui ,v j ) = wi + 2W. • Triplet completion arcs (red): ∀ j ∈ J, an arc (v j , t) with capacity c(v j ,t) = W m + 2. • Chain arcs (red): ∀ j ∈ J, an entry arc (v j , v1j ) and internal arcs (vlj , vlj+1 ) for l ∈ {1, . . . , N − 1}, each with capacity W
(n+1)(n−3) + 1. n
(n+1)(n−3) arc (v N + 2. j , t ) is added with capacity W n
9
An exit
• Bypass arcs: Three sets of arcs with a constant capacity of 2 are added to control delays: (ui , t) for all i ∈ I (green dashed), (s, v j ) for all j ∈ J (orange dashed), and (s, v N j ) for all j ∈ J (yellow dashed). We define three commodities sharing the same source s and destination t. The structure and purpose of each commodity are summarized below: • Commodity k L (Light and Fast): Size bL = W, maximum delay d L = 1 2 + 2W .
We will prove that it must be carried exclusively through paths of the form s → ui → v j → t, effectively building the solution to the 3-Partition problem. • Commodity k H (Heavy and Slow): Size b H = (m − 1)(n + 1)W, 1 maximum delay d H = N + 2 + W .
This commodity will use all paths crossing the partition arcs (ui , v j ) that are not used by k L . This creates high delays on these arcs, forcing k L to define a partition of the objects set I. • Commodity k2 (Delay calibration): Size b2 = 5m, maximum delay d2 = 2. We will show that this tight delay limit forces the commodity to use only 2-hop paths (formed by the bypass arcs) and to maintain a load of exactly 1 on each of these paths. This sets the delay and load on the crossed links.
Proposition 2.1.
If the 3-Partition instance with weights {wi }i∈ I is feasible,
then the related DCMCF instance described above admits a feasible solution with γ = 1. Proof. Assuming that the 3-Partition instance is feasible, each vertex v j is assigned to a single triplet Tj . We can build a multi-commodity flow using the following paths: • For commodity k L : for every triplet j ∈ J and object i ∈ Tj , the path s → ui → v j → t is used with a load equal to wi . 10
• For commodity k H : for every triplet j ∈ J and object i ∈ I \ Tj , the path s → ui → v j → v1j → · · · → v N j → t is used with a load equal to wi + W. • For commodity k2 : each path in {s → ui → t}i∈ I ∪ {s → v j → t } j∈ J ∪ { s → v N j → t } j∈ J is used with a load equal to 1. One can verify that each commodity sends the required load: ∑i∈ I wi = W = bL for commodity k L , ∑ j∈ J ∑i∈ I \Tj (wi + W ) = m W − W m + ( n − 3 )W = mW (n − 2 − m1 ) = (m − 1)(n + 1)W = b H for commodity k H and 2m + n = 5m = b2 for commodity k2 . The delay of each arc is given by: 1 1 • d(ui ,v j ) = (w +2W if i ∈ Tj ; = 2W )−w i
i
1 • d(ui ,v j ) = (w +2W )−( = W1 if i ∈ / Tj ; w +W ) i
i
• the delay of all other arcs is exactly equal to 1. It is easy to verify that the delay constraints are satisfied (with equality) for all paths used by all commodities. Let us now suppose that this DCMCF instance admits a solution with γ ≥ 1. We will prove that the corresponding 3-Partition instance is of True type. For this purpose, we will prove that commodities k2 , k L and k H are necessarily routed as described in the proof of Proposition 2.1, which allows us to infer the feasibility of the 3-Partition instance. Since the proof is relatively long, we will only show the intermediate lemmas below: all proofs can be found in the Appendix section at the end of the paper. Let us first prove that commodity k2 must follow a specific set of paths: Lemma 2.1.
Commodity k2 must necessarily follow paths in
{ s → ui → t }i ∈ I ∪ { s → v j → t } j∈ J ∪ { s → v N j → t } j∈ J .
The proof of this lemma is presented in Appendix A.1. It relies on the fact that the minimum delay of a given arc a ∈ A is c1a : we can show that, 11
for any path p from s to t not included in the set above, the minimum delay ∑ a∈ p c1a is greater than d2 . The next lemma states that the paths described in Lemma 2.1 are actually used by k2 . Lemma 2.2.
k2 uses all paths in {s → ui → t}i∈ I ∪ {s → v j → t} j∈ J ∪ {s →
vN j → t } j∈ J . This lemma is proved by assuming that one of the paths is not used and showing that the additional load carried on the remaining paths would increase the path’s delay above the commodity’s limits. The full proof can be found in Appendix A.2. In order to compute the exact load of commodity k2 over each used path, we define for each i ∈ I and j ∈ J the scalars ϵi , ϵ j , and ϵ′j in ] − 1, 1[ such that: y(ui ,t) = 1 + ϵi
∀i ∈ I,
y(s,v j ) = 1 + ϵ j
∀ j ∈ J,
y(s,v N ) = 1 + ϵ′j j
We also consider the sets Q I ⊂ I, Q J ⊂ J, and Q′J ⊂ J defined as follows: Q I = { i ∈ I | ϵi ̸ = 0 } ,
Q J = { j ∈ J | ϵ j ̸ = 0},
Q′J = { j ∈ J | ϵ′j ̸= 0}.
We will show in Lemma 2.5 that Q I ∪ Q J ∪ Q′J is necessarily empty. In order to prove this result, we will first give upper bounds on the load of arcs (s, ui ) for every i ∈ I in Lemma 2.3, and upper bounds on the load of arcs (v j , t) and (v N j , t ) for every j ∈ J in Lemma 2.4. Lemma 2.3.
For i ∈ I, the load of arc (s, ui ) is strictly less than mwi + (m −
1)W + 1 − ϵi if i ∈ Q I , and less than or equal to mwi + (m − 1)W + 1 if i ∈ I \ Q I . The proof of this lemma can be found in Appendix A.3. It relies on the fact that commodity k2 uses the arcs (ui , t) - enforcing a maximum delay of b2 = 2 on the path s → ui → t, and on a linear under-estimator of the delays of arcs (s, ui ) and (ui , t).
12
∀ j ∈ J.
Lemma 2.4.
For j ∈ J, the load of arc (v j , t) is strictly less than W m + 1 − ϵ j if
j ∈ Q J , and less than or equal to W m + 1 if j ∈ J \ Q J .
(n+1)(n−3) + 1 − ϵ′j if n (n+1)(n−3) j ∈ Q′J , and less than or equal to W + 1 if j ∈ J \ Q′J . n
Similarly, the load of arc (v N j , t ) is strictly less than W
The proof of this lemma, given in Appendix A.4, follows the same reasoning as the proof of Lemma 2.3. Based on Lemmas 2.3 and 2.4 above, we can establish the exact flow on several arcs of A: Lemma 2.5.
The delays on arcs (s, ui ), (v j , t), (v N j , t ) and on the bypass arcs are
equal to 1 for every i ∈ I and j ∈ J, and the loads on these arcs are: y(s,ui ) = mwi + (m − 1)W + 1 W +1 m (n + 1)(n − 3) y(v N ,t) = W +1 j n y(ui ,t) = y(s,v j ) = y(s,v N ) = 1 y(v j ,t) =
j
∀i ∈ I
(7)
∀j ∈ J
(8)
∀j ∈ J
(9)
∀ j ∈ J, i ∈ I.
(10)
This lemma is proven by summing the loads on all arcs exiting s and entering t, and showing that if the set of arcs Q I ∪ Q J ∪ Q′J is non-empty, this sum of loads is strictly lower than twice the size of the commodities k2 , k L , and k H , contradicting the possibility of a throughput γ ≥ 1. Equations (10) and Lemma 2.5 together imply that commodity k2 routes a unit load through each path in the set
{ s → ui → t }i ∈ I ∪ { s → v j → t } j∈ J ∪ { s → v N j → t } j∈ J . As a consequence, the arcs {(ui , t)}i∈ I , {(s, v j )} j∈ J , and {(s, v N j )} j∈ J are fully saturated by commodity k2 if its delay is satisfied, meaning they cannot be used by commodity k L or k H .
13
Let us now characterize the routing of commodity k L . Commodity k L must follow paths in {s → ui → v j → t}i∈ I,j∈ J .
Lemma 2.6.
The proof of this lemma, given in Appendix A.6, simply relies on the fact that all other paths are either saturated by commodity k2 or violate the delay limit d L . Lemma 2.7.
The load of commodity k L over each arc in {(v j , t)} j∈ J is exactly W m.
The proof of this lemma can be found in Appendix A.7 ; it directly results from the load of arc (v j , t) given in Equation (8). Let us now consider commodity k H . Lemma 2.8.
The load of commodity k H over each arc in {(v j , v1j )} j∈ J ∪ {(vlj , vlj+1 )} j∈ J,l ∈[1,N −1] ∪
(n+1)(n−3) {(v N , and the delay on each arc is equal to 1. j , t )} j∈ J is exactly W n
The proof of this lemma, which results from Equation (9), is given in Appendix A.8. The results presented above fix the flow on each arc entering vertices ui for i ∈ I and exiting vertices v j for j ∈ J if the concurrent throughput γ is greater than 1. We will now study the arcs (ui , v j ) to describe how the paths followed by commodity k L allow the construction of a 3-Partition of the original problem. The next lemma allows us to associate each object i ∈ I with a unique part j ∈ J in the original 3-Partition problem: Lemma 2.9.
For every i ∈ I, commodity k L is carried by a single arc exiting
vertex ui , and the load of k L on this arc is exactly wi . This arc does not carry commodity k H . This lemma is proved in Appendix A.9; this proof relies on the upper bound of the delays of arcs (ui , v j ) if commodities k L and k H cross them, and on the total flow exiting the nodes ui — obtained by flow conservation and Equation (7). Lemma 2.10.
For every j ∈ J, commodity k L is carried by exactly 3 arcs entering
vertex v j . 14
This result is proved by using the possible loads of arcs (ui , v j ), which depend on the commodities they carry, as shown in Lemma 2.9, and the flow conservation at node v j . Proposition 2.2.
If the DCMCF instance described above has a feasible solution
of value γ = 1, the 3-Partition instance with weights {wi }i∈ I is of type True. Lemmas 2.9 and 2.10 showed that if the DCMCF instance is feasible, the arcs (ui , v j ) crossed by commodity k L allow the construction of triplets of objects (and that each arc carries a load wi ) ; flow conservation and Equation (8) allow us to conclude that the sum of weights of each triplet is W m , showing that the 3-Partition instance was feasible. The complete proof is given in Appendix A.11. Theorem 2.1. DCMCF is strongly NP-hard, even when there are at most 3 commodities, all sharing the same source and destination, and when every path from the source to the destination can potentially be used by each commodity. Proof. This is a direct consequence of Propositions 2.1 and 2.2 and the strong NP-hardness of 3-Partition.
3
Relaxation of the delay constraints
Constraints (3) rewritten as (6) are the “difficult” constraints of the DCMCF problem.
xk
In fact, the function g p : { x kp , (y a ) a∈ p } → ∑ a∈ p ca −pya − x kp dk
is a non-convex function.
One way to get good convex relaxations of
DCMCF consists of replacing, for every k ∈ K and p ∈ Pk , constraint g p ({ x kp , (y a ) a∈ p }) ≤ 0 by constraint h p ({ x kp , (y a ) a∈ p }) ≤ 0 where h p is convex and satisfies h p ≤ g p . Since g p is an additive function with a delay term for each arc of p, it is natural to decompose the problem by considering all terms separately. This leads to the study of the function f defined by f ( x, y) = 1−x y for ( x, y) ∈ [0, 1]2 . Constraints (6) can then be formulated as:
15
bk x kp y a
∑ f ( ca , ca ) ≤ bk xkp × dk
∀k ∈ K, p ∈ Pk .
(11)
a∈ p
To obtain good convex relaxations, one can then focus on the convex envelope of f . More precisely, one can notice that, for every k ∈ K, p ∈ Pk and a ∈ A, the domain of
bk x kp ya 2 c a and c a is narrower than [0, 1] :
bk x kp ya ca ≤ ca . y - Inequality (3) ensures that caa < 1 (otherwise the delay of link a would
- Inequality (2) ensures that
be infinite, violating the delay constraint).
- Finally, both the x kp and y a variable are nonnegative. Therefore we will compute the convex envelope fˇ of f on the polyhedral subset Xϵ,θ,ζ,η defined for (ϵ, ζ, η, θ ) in ]0, 1[2 ×[0, 1]2 by: Xϵ,θ,ζ,η = {( x, y) ∈ [0, 1]2 : y ≥ x + θ, y ∈ [η, 1 − ϵ], x ≤ 1 − ζ }.
(12)
As will be shown in Section 3.6, given some p ∈ Pk and a ∈ p, inequalities relating x kp and y a can be easily used to deduce possible values of
(ϵ, θ, ζ, η ) ∈ [0, 1]4 . Note that these values will depend on p and a and one can solve some intermediate convex problems to get the best values. Before providing complete details in Section 3.6, let us start for now by computing the convex envelope of f on Xϵ,θ,ζ,η . Let us first divide Xϵ,θ,ζ,η into 3 polyhedral subsets (see Figure 2 for illustration) Xϵ,θ,ζ,η = Rϵ,θ,η ∪ Sϵ,θ,ζ,η ∪ Tϵ,θ,ζ , where
Rϵ,θ,η =
( x, y) ∈ [0, 1]2 :y ≥ η, y ≤ 1 − ϵ −
1−ϵ−η x η−θ
1−ϵ−η ζ−ϵ−θ Sϵ,θ,ζ,η = ( x, y) ∈ [0, 1] :y ≥ x + θ, y ≥ 1 − ϵ − x, y ≤ 1 − ϵ − x η−θ 1−ζ ζ−ϵ−θ Tϵ,θ,ζ = ( x, y) ∈ [0, 1]2 :y ≤ 1 − ϵ, x ≤ 1 − ζ, y ≥ 1 − ϵ − x . 1−ζ
2
Notice that the partition makes sense (i.e., the 3 subsets are well-defined) only if 0 ≤ θ ≤ η ≤ 1 − ζ + θ ≤ 1 − ϵ ≤ 1.
(13)
We will compute the convex envelope of f on each of the subsets Rϵ,θ,η ,
Sϵ,θ,ζ,η and Tϵ,ζ,η . Then we will show that they can be combined to obtain
16
the convex envelope on Xϵ,θ,ζ,η . 𝑦 1−𝜖 𝒯𝜖,𝜃,𝜁
𝒮𝜖,𝜃,𝜁,𝜂
𝜂
ℛ𝜖,𝜃,𝜂
𝜃 𝜂−𝜃
1−𝜁
𝑥
Figure 2: Representation of the domain Xϵ,θ,ζ,η of the function f , and its partition in Rϵ,θ,η ∪ Sϵ,θ,ζ,η ∪ Tϵ,θ,ζ .
3.1
Convex envelope of f on Rϵ,θ,η
Consider the function rη : Xϵ,θ,ζ,η → R where rη ( x, y) = 1−x η . Proposition 3.1.
rη is a convex under-estimator of f on Xϵ,θ,ζ,η (i.e., ∀( x, y) ∈
Xϵ,θ,ζ,η , rη ( x, y) ≤ fˇXϵ,θ,ζ,η ( x, y) ≤ f ( x, y)). When f is restricted to Rϵ,θ,η , its convex envelope is given by rη (i.e., fˇRϵ,θ,η = rη ). Proof. rη is linear and thus convex. We also have rη ≤ f on Xϵ,θ,ζ,η since y ≥ η. So rη is a convex under-estimator of f . To show that it is the convex envelope of f on Rϵ,θ,η , let us show that fˇR ( x, y) ≤ rη ( x, y), ∀( x, y) ∈ Rϵ,θ,η . ϵ,θ,η
Observe that ( x, y) ∈ Rϵ,θ,η can be written as α( x0 , η ) + (1 − α)(0, 1 − ϵ) 1− ϵ − η
with α = xx0 ∈ [0, 1] and x0 = x 1−ϵ−y . Note that ( x0 , η ) and (0, 1 − ϵ)
both belong to Rϵ,θ,η , and that rη ( x, y) = α f ( x0 , η ) + (1 − α) f (0, 1 − ϵ). By convexity of fˇR , we must have rη ≥ fˇR , and thus rη is the convex ϵ,θ,η
ϵ,θ,η
envelope of f restricted to Rϵ,θ,η .
17
3.2
Convex envelope of f on Sϵ,θ,η,ζ
We define the function sϵ,θ : Xϵ,θ,ζ,η → R as sϵ,θ ( x, y) = 1−θ − x x 1−
( x, y) ̸= (0, 1 − ϵ), and sϵ,θ (0, 1 − ϵ) = 0.
if
y− x −θ 1− ϵ − θ
sϵ,θ is a convex under-estimator of f on Xϵ,θ,ζ,η . When f is = sϵ,θ ). restricted to Sϵ,θ,ζ,η , its convex envelope is given by sϵ,θ (i.e., fˇS
Proposition 3.2.
ϵ,θ,ζ,η
Proof. Let us first check that the denominator of sϵ,θ ( x, y) is strictly positive. Observe that 1 − θ −
x y− x −θ 1 − 1− ϵ − θ
= 1 − θ − x 1−1−ϵ−ϵ−y+θ x . 1 − ϵ − y + x is non-zero
on Xϵ,θ,ζ,η if ( x, y) ̸= (0, 1 − ϵ). Using y − x ≥ θ, we get 1 − θ −
x y− x −θ 1 − 1− ϵ − θ
≥
1 − θ − x ≥ 1 − y ≥ ϵ > 0. sϵ,θ is then well-defined on Xϵ,θ,ζ,η and positive. It is also easy to prove the continuity of the function at (0, 1 − ϵ) since lim(x,y)→(0,1−ϵ) sϵ,θ ( x, y) = 0 = sϵ,θ (0, 1 − ϵ). To prove the convexity of sϵ,θ on Xϵ,θ,ζ,η , one can for example use the fact that the perspective function of a convex function is also convex. Consider the function f θ defined on [0, 1[ by f θ ( x ) = f ( x, x + θ ) = 1−xx−θ . f θ is obviously convex. Therefore, its perspective function p defined as y− x −θ
ps ( x, t) = t f θ ( x/t) = 1−θx−x/t is convex. Since sϵ,θ ( x, y) = ps ( x, 1 − 1−ϵ−θ ) is the composition of a convex and an affine function, sϵ,θ is convex. To show that sϵ,θ is an under-estimator of f over Xϵ,θ,ζ,η for x > 0, we s
( x,y)
1− y
should prove that, for ( x, y) ∈ Xϵ,θ,ζ,η , ϵ,θ = 1− θ − f ( x,y)
x y− x −θ 1− 1− ϵ − θ
y)(1−ϵ+ x −y) = (1−θ )((11− −ϵ+ x −y)− x (1−ϵ−θ )
is less than 1. Considering the difference between the numerator and the denominator we get: (1 − y)(1 − ϵ + x − y) − (1 − θ )(1 − ϵ + x − y) + x (1 − ϵ − θ ) = (θ + x − y)(1 − ϵ − y)
which is obviously non-positive on the set Xϵ,θ,ζ,η . For x = 0, both functions are equal to 0. Finally, let us restrict f to Sϵ,θ,ζ,η . Since sϵ,θ is a convex under-estimator of f , we already have fˇS ≥ sϵ,θ . For the other direction, given any ϵ,θ,ζ,η
( x, y) ∈ Sϵ,θ,ζ,η , let α = 1−1−ϵ+ϵ−x−θ y and x0 = y0 − θ = αx . Observe that ( x0 , y0 ) and (0, 1 − ϵ) are both in Sϵ,θ,ζ,η , and ( x, y) is a convex combination
18
of ( x0 , y0 ) and (0, 1 − ϵ): ( x, y) = α( x0 , y0 ) + (1 − α)(0, 1 − ϵ). Moreover, one can easily check that sϵ,θ ( x, y) = α f ( x0 , y0 ) + (1 − α) f (0, 1 − ϵ). By ≤ sϵ,θ . , we deduce that fˇS convexity of fˇS ϵ,θ,ζ,η
ϵ,θ,ζ,η
The next proposition states that a constraint of form sϵ,θ ( x, y) ≤ d can be expressed through second-order cone programming. sϵ,θ ( x, y) ≤ d can be expressed as the hyperbolic constraint x −θ 1 (z + d)(z − 1−θ x ) ≥ z2 and the linear constraint z = 1 − y1− −ϵ−θ .
Proposition 3.3.
y− x −θ
Proof. Let z = 1 − 1−ϵ−θ . Then: sϵ,θ ( x, y) ≤ d
⇐⇒
x ≤d 1 − θ − xz
⇐⇒
1 1−θ xz +z ≤ z+d 1 z − 1− θx
z2
⇐⇒
1 z − 1− θx (14)
Using the fact that (z − 1−1 θ x ) is strictly positive (from the first part of the proof of Proposition 3.2), the last inequality is equivalent to z2 ≤
(z + d)(z − 1−1 θ x ). Note that Proposition 3.3 provides a second proof of the convexity of sϵ,θ since its epigraph is shown to be convex.
3.3
Convex envelope of f on Tϵ,θ,ζ 2
x Consider the function tϵ,ζ : Xϵ,θ,ζ,η → R where tϵ,ζ ( x, y) = (1−ζ )(1−ϵ)+ ϵx −(1−ζ )y
if ( x, y) ̸= (0, 1 − ϵ), and tϵ,ζ (0, 1 − ϵ) = 0.
tϵ,ζ is a convex under-estimator of f on Xϵ,θ,ζ,η . When f is restricted to Tϵ,θ,ζ , its convex envelope is given by tϵ,ζ (i.e., fˇS = tϵ,ζ ). Proposition 3.4.
ϵ,θ,ζ,η
Proof. The proof is similar to the proof of Proposition 3.2. First, the denominator in the fraction that defines tϵ,ζ is strictly positive. Indeed, (1 − ζ )(1 − ϵ) + ϵx − (1 − ζ )y = (1 − ζ )(1 − ϵ − y) + ϵx > 0 if ( x, y) ∈ Xϵ,θ,ζ,η \ {(0, 1 − ϵ)}.
So tϵ,ζ is well-defined on Xϵ,θ,ζ,η .
It
is also easy to prove the continuity of the function at (0, 1 − ϵ) since lim(x,y)→(0,1−ϵ) tϵ,ζ ( x, y) = 0 = tϵ,ζ (0, 1 − ϵ). 19
≤ z + d.
Convexity of tϵ,ζ can be proven by considering the convex function f ζ −ζ defined on [−∞, 1 − ϵ] by f ζ (y) = f (1 − ζ, y) = 11− y . Because f ζ is convex,
its perspective function pt defined as pt ( x, t) = t f ζ ( xt ) =
t2 (1− ζ ) t−y is convex.
Since tϵ,ζ ( x, y) = pt (y − (1 − 1−x ζ )(1 − ϵ), 1−x ζ ) is the composition of a convex and an affine function, tϵ,ζ is convex. To show that tϵ,ζ is an under-estimator of f over Xϵ,θ,ζ,η for x > 0, tϵ,ζ ( x,y) f ( x,y)
1− y ) = (1−ζ )(1−xϵ()+ ϵx −(1−ζ )y is less than 1. Considering the difference between the numerator and the denominator, we get:
we should prove that, for ( x, y) ∈ Xϵ,θ,ζ,η ,
x − yx − (1 − ζ )(1 − ϵ) − ϵx + (1 − ζ )y = (1 − ϵ)(1 − ζ − x ) + y(1 − ζ − x ) = −(1 − ϵ − y)(1 − ζ − x )
which is obviously nonpositive on Xϵ,θζ,η (for x = 0, we have f ( x, y) = tϵ,ζ ( x, y) = 0). Finally, let us consider the restriction of f to Tϵ,θ,ζ . As tϵ,ζ is a convex under-estimator of f , it satisfies tϵ,ζ ( x, y) ≤ fˇT ( x, y). Observe that each ϵ,ζ
( x, y) of Tϵ,θ,ζ can be expressed as a convex combination of two members of Tϵ,θ,ζ : ( x, y) = α(1 − ζ, y0 ) + (1 − α)(0, 1 − ϵ), with α = 1−x ζ and y0 = y 1−x ζ − (1−ζ )(1−ϵ) + 1 − ϵ. Moreover, one can easily check that tϵ,ζ ( x, y) = α f (1 − x
ζ, y0 ) + (1 − α) f (0, 1 − ϵ) proving, by convexity of fˇTϵ,θ,ζ , that tϵ,ζ ( x, y) ≥ fˇT ( x, y). ϵ,θ,ζ
Remark 3.1.
The constraint tϵ,ζ ( x, y) ≤ d can be expressed through second-order
cone programming since the inequality d × ((1 − ζ )(1 − ϵ) + ϵx − (1 − ζ )y) ≥ x2 is a convex hyperbolic constraint. Note that Remark 3.1 also allows to prove convexity of tϵ,ζ .
3.4
Convex envelope of f on Xϵ,θ,ζ,η
Theorem 3.1. The convex envelope of f on Xϵ,θ,ζ,η is given by: fˇXϵ,θ,ζ,η ( x, y) = max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)) fˇXϵ,θ,ζ,η ( x, y) = max(
x x , 1−η 1−θ−
x
y− x −θ
1 − 1− ϵ − θ
20
,
x2 ). (1 − ζ )(1 − ϵ) + ϵx − (1 − ζ )y
(15)
Proof. From Propositions 3.1, 3.2 and 3.4, max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)) is ≥ max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)). a convex under-estimator of f on Xϵ,θ,ζ,η , showing that fˇX ϵ,θ,ζ,η
To show equality, first observe that Rϵ,θ,η ⊂ Xϵ,θ,ζ,η implies that fˇXϵ,θ,ζ,η ( x, y) ≤ fˇRϵ,θ,η ( x, y) for any ( x, y) ∈ Rϵ,θ,η . ( x, y) for any ( x, y) ∈ Sϵ,θ,η,ζ , and fˇX ( x, y) ≤ fˇS Similarly, fˇX ϵ,θ,η,ζ
ϵ,θ,ζ,η
fˇTϵ,θ,ζ ( x, y) for any ( x, y) ∈ Tϵ,θ,ζ . = sϵ,θ and fˇT = rη , fˇS Using that fˇR ϵ,θ,η,ζ
ϵ,θ,η
ϵ,θ,ζ
ϵ,θ,ζ,η
( x, y) ≤
= tϵ,ζ , we deduce that:
∀( x, y) ∈ Rϵ,θ,η ,
fˇXϵ,θ,ζ,η ( x, y) ≤ rη ( x, y) = max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)),
∀( x, y) ∈ Sϵ,θη,ζ ,
fˇXϵ,θ,ζ,η ( x, y) ≤ sϵ,θ ( x, y) = max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)),
∀( x, y) ∈ Tϵ,θ,ζ ,
fˇXϵ,θ,ζ,η ( x, y) ≤ tϵ,ζ ( x, y) = max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)).
Since Xϵ,θ,ζ,η = Rϵ,θ,η ∪ Sϵ,θ,η,ζ ∪ Tϵ,θ,η , fˇXϵ,θ,ζ,η ( x, y) ≤ max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)) for any ( x, y) ∈ Xϵ,θ,ζ,η . Figure 3 illustrates the difference between the values of the function f and those of its under-estimators, highlighting the tightness of the relaxation. Observe that the relaxation is tighter when x is large or when y − x is small, corresponding respectively to high path usage and low arc usage by the other paths in the DCMCF problem.
Figure 3: Values and multiplicative errors of rη , sϵ,θ , tϵ,θ and fˇXϵ,θ,ζ,η with ϵ = 0.1, ζ = 0.3, η = 0.1, and θ = 0. Values are lower (in blue) when relaxations are closer to the actual value of f . Proposition 3.5.
A constraint of the type fˇXϵ,θ,ζ,η ( x, y) ≤ d, ∀( x, y) ∈ Xϵ,θ,ζ,η
can be formulated as a set of second-order cone programming constraints. Proof. A constraint of type fˇXϵ,θ,ζ,η ( x, y) = max(rη ( x, y), sϵ,θ ( x, y), tϵ,ζ ( x, y)) ≤ 21
d can be expressed as a set of 3 constraints rη ( x, y) ≤ d, sϵ,θ ( x, y) ≤ d and tϵ,ζ ( x, y)) ≤ d. From Proposition 3.3 and Remark 3.1, the last two constraints can be formulated as second-order cone constraints, and the first one is linear.
3.5
Relaxation of the DCMCF problem
Constraints (11) provide a reformulation of the delay constraints (3) of the DCMCF problem based on the function f . From this reformulation and the convex envelope of the function f , the delay constraints of the DCMCF problem can be relaxed as:
∑ fˇX −
a∈ p
k k k c a u a , l a p , c a −b u p , l a ca ca ca ca
(
bk k y a x , ) ≤ dk bk x kp ca p ca
∀k ∈ K, p ∈ Pk
(16)
where u a (resp. ukp ) is an upper bound of y a (resp. x kp ), and la is (resp. la kp ) a lower bound on y a (resp. y a − bk x kp ). Details about the computation of these parameters are deferred to Section 3.6. pk Using the analytical expression of fˇ, and adding a variable d a to express the term bk1uk fˇX p
DCMCF:
k
k k k c a −u a , l a p , c a −b u p , l a ca ca ca ca
( bca x kp , ycaa ), we get the following relaxation of
22
DCMCFenv :
max γ (1), (2),
(17) x kp
∑ d a − uk dk ≤ 0 pk
∀k ∈ K, p ∈ Pk ,
(18)
∀k ∈ K, p ∈ Pk , a ∈ p,
(19)
− da ≤ 0
pk
∀k ∈ K, p ∈ Pk , a ∈ p,
(20)
− da ≤ 0
pk
∀k ∈ K, p ∈ Pk , a ∈ p,
(21)
x kp ≥ 0
∀k ∈ K, p ∈ Pk ,
(22)
x kp ≤ ukp
k
∀k ∈ K, p ∈ P ,
(23)
ya ≤ ua
k
∀k ∈ K, p ∈ P , a ∈ p,
(24)
k
(25)
a∈ p
p
x kp ukp
pk
ca − la
− da ≤ 0 x kp ukp
(u a −la k ) c a − la kp − u −(y −bpk xk ) bk x kp a a p xk
( ukp )2 p
xk xk c a ukp − y a + (1 − ukp )u a p p
y a ≥ bk x kp + la kp
∀k ∈ K, p ∈ P , a ∈ p,
where Constraints (18) represent the relaxed delay constraint and Constraints (19), (20) and (21) represent the respective contributions of functions r l a , s c −u ca
a
ca
l k a , ap ca
and t c −u a
ca
c −bk ukp a, a ca
to the envelope function. Constraints (22) to
(25) describe, for k ∈ K, p ∈ Pk and a ∈ A the feasible domain for variables x kp and y a on which the convex envelopes of the delay functions are built. From Proposition 3.5, one can observe that the DCMCFenv problem can be formulated as a second-order cone program.
3.6
Computation of a tight domain
The DCMCFenv relaxation relies on the bounds la , u a (lower and upper bounds of y a for a ∈ A), ukp (upper bound of x kp for k ∈ K, p ∈ Pk ) and la kp (lower-bound of y a − bk x kp for k ∈ K, p ∈ Pk and a ∈ p). As suggested in [4], explicit upper bounds for y a can be computed by exploiting the observation that the load on each arc of the graph is induced by paths whose delays must satisfy some constraints. Therefore, 23
for any a ∈ A, there exists a k ∈ K and p ∈ P such that a ∈ p and
≤ dk which allows to compute the following upper bound on y a : u a = max p∋a c a − dk − 1 1 . On the other hand, l a = 0 is a 1 1 c a −y a + ∑ a′ ∈ p,a′ ̸= a c a
valid lower-bound of y a .
∑ a′ ∈ p,a′ ̸= a c a
For every k ∈ K and p ∈ Pk , the load generated by path p, bk x kp , is simply bounded by the minimum upper bound of the loads over all arcs used by p, which gives the following upper bound on x kp : ukp = mina∈ p ubka . Finally,
la kp = 0 is a valid lower-bound on the residual load on an arc a ∈ A for a given commodity k ∈ K and path p ∈ Pk . It is also possible to compute tighter bounds by considering a feasible solution of the DCMCF problem and solving, for every arc a, commodity k and path p, a convex problem minimizing (resp. maximizing) the higher (resp. lower) bounds for the y a , x kp , and y a − bk x kp values under the constraints of the DCMCFenv problem. For instance, given a feasible flow γ0 and initial bounds for every variable, a tighter value of u a′ for a′ ∈ A can be computed by solving the following convex problem: max y a′ (1), (2), (18), (19), (20), (21), (22), (23), (24), (25), γ ≥ γ0 .
Similar problems can be considered to compute tighter values of ukp , la , la kp for every k ∈ K, p ∈ Pk and a ∈ A.
4
Alternative formulations of the DCMCF problem
4.1
A Big-M formulation
The delay constraints (3) can be expressed as mixed-integer constraints by introducing binary variables zkp indicating whether a path p is used. Using upper bounds dkp
max
on the delay of path p when zkp = x kp = 0, which play
the role of Big-M constants, the DCMCF problem can be written as:
24
DCMCFBig-M :
max γ (1), (2), (22), (24) x kp ≤ ukp zkp
∀k ∈ K, p ∈ Pk
(26)
∀ p ∈ Pk
(27)
∀k ∈ K, p ∈ Pk .
(28)
max 1 ∑ ca − ya ≤ dk zkp + dkp (1 − zkp ) a∈ p
zkp ∈ {0, 1}
Note that the strength of the Big-M relaxation strongly depends on the tightness of the dkp
max
bounds. However, the DCMCFBig-M formulation en-
ables a straightforward implementation of branch-and-bound approaches using commercial solvers. Tighter relaxations of the delay constraints such as the one proposed in Section 3.5 can also be included in the DCMCFBig-M problem to provide a more efficient relaxation of DCMF.
4.2
A disjunctive-programming-based relaxation
We describe a relaxation proposed in [16] and we prove that DCMCFenv provides tighter bounds than the disjunctive-programming-based relaxation. The delay constraint related to a path p is relaxed as follows. The authors consider the convex envelope of Γ0 kp ∪ Γ1 kp where Γ0 kp =
n (
Γ1 kp =
o zkp , (y a ) a∈ p : zkp = 0, la ≤ y a ≤ u a , ∀ a ∈ p , and
1 ≤ dk c − ya a a∈ p
zkp , (y a ) a∈ p : zkp = 1, la ≤ y a ≤ u a , ∀ a ∈ p, ∑
) .
Then they derive the following relaxation of the DCMCF problem: DCMCFred
max γ (1), (2), (22), (24), (26), zkp
2
∑ c zk − y k ≤ zkp dk
∀k ∈ K, p ∈ Pk
(29)
y a − (1 − zkp )u a ≤ y a kp ≤ y a
∀k ∈ K, p ∈ Pk , a ∈ p
(30)
zkp la ≤ y a kp ≤ zkp u a
∀k ∈ K, p ∈ Pk , a ∈ p
(31)
k
(32)
a∈ p a p
ap
zkp ≥ 0
∀k ∈ K, p ∈ P .
25
where new variables y a kp are introduced for every commodity k ∈ K, path p ∈ Pk and arc a ∈ p. Notice that this relaxation is the strongest one among those proposed in [16]. Proposition 4.1.
DCMCFenv dominates DCMCFred .
Proof. Starting from a feasible solution of DCMCFenv , we build a feasible solution of DCMCFred with the same objective value.
Let then ( x̃ kp )k∈K, p∈ Pk , (ỹ a ) a∈ A , γ̃ be a feasible solution of DCMCFenv , , γ̄ denote and let ( x̄ kp )k∈K, p∈ Pk , (z̄kp )k∈K, p∈ Pk , (ȳ a ) a∈ A , (ȳ a kp ) k k ∈K,p∈ P ,a∈ p
the solution that we aim to construct. We fix the variable values as follows: x̄ kp = x̃ kp ,
z̄kp =
ȳ a = ỹ a ,
x̄ kp ukp
ȳ a kp = max(ȳ a − (1 − z̄kp )u a , z̄kp la ),
,
γ̄ = γ̃.
All constraints of DCMCFred , except (29), are straightforwardly satisfied. As Constraints (18), (19) and (21) are satisfied, we necessarily have: z̄kp
z̄kp
2
∑ max( ca − la , c z̄k − ȳ + (1 − z̄k )u ) − z̄kp dk ≤ 0
a∈ p
a p
a
p
∀k ∈ K, p ∈ Pk .
a
z̄k
z̄k
2
p )= If ȳ a − (1 − z̄kp )u a ≥ z̄kp la , then ȳ a kp = ȳ a − (1 − z̄kp )u a , and max( ca −p la , c z̄k −ȳ +( 1−z̄k )u a p
z̄kp . Conversely, if ȳ a − (1 − z̄kp )u a ≤ z̄kp la , then ȳ a kp = z̄kp la , and c a z̄kp −ȳ a kp
max(
z̄kp
z̄kp
,
2
c a − la c a z̄kp − y a + (1 − z̄kp )u a
)=
z̄kp ca − la
=
z̄kp
2
c a z̄kp − ȳ a kp
.
This ensures that Constraints (29) are satisfied in both cases, proving the feasibility of the constructed solution of DCMCFred with γ̄ = γ̃.
4.3
Additional valid constraints
Two additional sets of valid constraints can be considered in DCMCF relaxations. If variables zkp are considered, then we can obviously write:
∑ zkp ≥ 1
∀k ∈ K.
p∈ Pk
26
(33)
a
p
a
While the delay Constraints (6) are not convex, weighting them by the commodity size and aggregating them over all commodities and paths leads to a new convex constraint: x kp
∑ bk ∑ ∑ ca − ya ≤ ∑ bk ∑ dk xkp
k∈K
p∈ Pk a∈ p
k∈K
⇔
p∈ Pk
∑
∑
bk x kp
c − ya a∈ A k ∈K,p∈ Pk | a∈ p a
≤ ∑ bk γdk
⇔
a∈ A
k∈K
(34)
Observe that (34) can be expressed through SOCP. These two constraints were tested numerically, but did not provide any significant impact on the problem’s resolution. Therefore, the numerical experiments measuring their impact are not reported in Section 6.
5
Lower bound heuristics and performance guarantees
Having derived upper bounds through the proposed relaxations, we now turn to the question of lower bounds. We begin with a result that may be viewed as negative, and then introduce several heuristics. In particular, we show that an heuristic based on the relaxation DCMCFenv constitutes an approximation algorithm with provable performance guarantees.
5.1
A negative results on heuristics
This section identifies a general limitation of heuristics applied to problems involving conditional constraints. We define the term convex restriction as the counterpart to a convex relaxation: the convex restriction of a domain is a convex subset of that domain. Similarly, the convex restriction of a constraint is a convex constraint that, if satisfied, guarantees the satisfaction of the original constraint. We demonstrate that building a convex restriction of a conditional constraint reduces to a binary discrete choice: either fully activating the constraint or forcing the trigger variable to zero.
27
ya
∑ c a − y a ≤ γ ∑ dk bk . k∈K
Theorem 5.1. Let E ⊆ R+ × Rn be a set and f be a continuous function E → R. Consider the conditional constraint f ( x, y) ≤ 0
if
x > 0 for variables
( x, y) ∈ E. Any convex restriction of this constraint on E is either a restriction of the constraint f ( x, y) ≤ 0 or a restriction of the constraint x = 0. Proof. The proof results directly from Lemma 5.1 presented below. Theorem 5.1 shows that there is no intermediate convex restriction for a conditional constraint and that any heuristic must make a distinct choice for each conditional constraint: it must either enforce the inequality f ( x, y) ≤ 0 unconditionally or force the value of the trigger variable x to zero. Consequently, any heuristic approach using convex restrictions is simply a constraint-selection process. To build a feasible solution, the algorithm must divide the conditional constraints into an active set, for which the constraint f ( x, y) ≤ 0 must be satisfied, and an inactive set, where the variables driving the conditions are forced to zero. This result proves that searching for continuous convex restrictions for conditional constraints is futile. Instead, heuristic design must focus entirely on the combinatorial selection of the active constraints. Once this selection is made, the algorithm solves the resulting problem to obtain a feasible solution. If the original problem only involves convex (conditional) constraints and a convex objective function, this resulting problem is convex and computationally easy to solve. Lemma 5.1.
Let E ⊆ R+ × Rn be a set and f : E → R be a continuous
function. Any convex subset of {( x, y) ∈ E | x f ( x, y) ≤ 0} is either included in
{( x, y) ∈ E | f ( x, y) ≤ 0} or in {( x, y) ∈ E | x = 0}. Proof. Let us define the following sets: D = {( x, y) ∈ E | x f ( x, y) ≤ 0} Don = {( x, y) ∈ E | f ( x, y) ≤ 0} Doff = {( x, y) ∈ E | x = 0}. 28
Because x ≥ 0 for all ( x, y) ∈ E, the condition x f ( x, y) ≤ 0 is logically equivalent to x = 0 or f ( x, y) ≤ 0. Therefore, D = Don ∪ Doff . Assume there exists a convex set D ′ ⊆ D that is neither included in Don nor in Doff . There exist two points poff = ( xoff , yoff ) ∈ D ′ \ Doff (so xoff > 0) and pon = ( xon , yon ) ∈ D ′ \ Don (so f ( xon , yon ) > 0)
Figure 4 illustrates this proof for E = [0, 1]2 and f ( x, y) = x2 + y2 − 41 . The domain D is the union of three disjoint subsets: Don ∩ Doff in red, D \ Doff in orange, and D \ Don in green. As we will see, a set containing both pon and poff is either non-convex or contains points outside D. 𝑦 1 𝑝𝑜𝑛 𝑝𝛼
𝑝𝑜𝑓𝑓
𝑥 0
1
Figure 4: Illustration of the proof of Lemma 5.1 for E = [0, 1]2 , and f ( x, y) = x2 + y2 − 41 .
Since poff ∈ D ′ ⊆ D and xoff > 0, we must have f ( xoff , yoff ) ≤ 0.
Similarly, since pon ∈ D and f ( xon , yon ) > 0, we must have xon = 0.
Because f is continuous on E and f ( xon , yon ) > 0, there exists a ball B centered at pon with radius r > 0 such that f ( x, y) > 0 for all ( x, y) ∈ E ∩ B . Consider the convex combination pα = ( xα , yα ) = (1 − α) pon + αpoff
with α = 2∥ p r− pon ∥ ∈]0, 1]. off
• ∥ pα − pon ∥ = α∥ poff − pon ∥ < r, so pα ∈ B and f ( pα ) > 0. • xα = (1 − α) xon + αxoff = αxoff > 0.
Therefore, xα f ( xα , yα ) > 0 and pα ∈ / D which implies that pα ∈ / D ′ and D ′ cannot be a convex set. This proves that there is no convex subset of D that is neither a convex subset of Don nor Doff .
29
5.2
Active subset heuristics
Following Theorem 5.1, the main principle of the heuristics we propose is to select a subset of paths Qk ⊂ Pk for each k ∈ K, and to replace the constraints (3) by the constraints ∑ a∈ p ca −1 ya ≤ dk for each p ∈ Qk , and to set
x kp to 0 for all paths in Pk \ Qk . All that remains is to solve a convex problem: DCMCFsubset max γ (1), (2), (4), (5) 1
∑ c a − y a ≤ dk
∀k ∈ K, p ∈ Qk .
a∈ p
DCMCFsubset is a simple convex optimization problem. The difficulty, of course, is guessing the right subset of paths to select. 5.2.1
All paths heuristic
Remember that we assumed that ∑ a∈ p c1a < dk for each path p ∈ Pk . One can then simply solve DCMCFsubset with Qk = Pk for every commodity k ∈ K to obtain a feasible solution of the problem with a strictly positive objective value, that will be called H all paths . 5.2.2
Greedy heuristic
The H all paths heuristic can be improved in a greedy fashion: the DCMCFsubset problem is first solved with Qk = Pk for every k ∈ K, then the path with the smallest x kp value is removed. This process is repeated as long as the objective function of the problem increases. This heuristic, called H greedy is presented in Algorithm 1, where OPT(DCMCF{Qk }k∈K ) is the optimal value of the DCMCFsubset problem on the subsets Qk of Pk for k ∈ K. 5.2.3
Heuristic based on the DCMCFenv Relaxation
It also makes sense to use the convex relaxation solution of Section 3 to select the subsets Qk . For example, for a given scalar S ∈ R+ , we can select all paths for which x kp ≥ | Pγk | in the convex relaxation’s optimal solution: QkS = { p ∈ Pk : x kp ≥ S|γPk | }. Let us denote this heuristic by Hthreshold . If 30
Algorithm 1 Greedy Heuristic Algorithm ∀ k ∈ K: Qk ← Pk H = 0, H − = OPT(DCMCF{Qk }k∈K ) − while H ≥ H do (k− , p− ) = argmin{ x kp | x kp > 0, ∑ a∈ p ca −1 ya = dk } −
−
Qk = Qk \ { p− } H = H−, H − = OPT(DCMCF{Qk }k∈K ) end while return H
S ≥ 1 then | QkS | ≥ 1 for every commodity k ∈ K, and the heuristic Hthreshold provides a strictly positive lower-bound for the DCMCF problem. Before analyzing the performance guarantees of Hthreshold in Section 5.3, we will present a lower bound of the optimal objective value of DCMCF that can be easily expressed and polynomially encoded in the size of the problem instance. While this bound is generally rather loose, it will nonetheless be used in the analysis of Hthreshold in the next section. Lemma 5.2.
There exists a feasible solution γ of DCMCF such that: 1 − d1k ∑ a∈ p c1a . γ ≥ γlow = min ′ k ∈K,p∈ Pk ∑k′ ∈K bk
(35)
Proof. Let γopt be the optimal value of γ when DCMCF is solved exactly. Then, there is at least one commodity k, and one path p ∈ Pk such that ∑ a∈ p ca −1 ya = dk . Moreover, for any a ∈ p, starting from ca −1 ya ≤ dk , y ca k we get that ca −aya ≤ y a dk which can be written as ca − y a ≤ 1 + y a d . Dik
viding by c a leads to ca −1 ya ≤ c1a + y a dca . Therefore, dk = ∑ a∈ p ca −1 ya ≤ ′
k
∑ a∈ p c1a + y a dca . By bounding y a by γopt (∑k′ ∈K bk ), we get that dk ≤ ∑ a∈ p c1a + ′ dk γopt (∑k′ ∈K bk ) ∑ a∈ p c1a , leading to inequality (35).
5.3
Performance guarantees of Hthreshold
We show that Hthreshold , when applied with an appropriately chosen threshold, constitutes an approximation algorithm with provable performance 31
guarantees. Because the complete proof is relatively long, we only present the main steps in this document: all intermediate computations can be found in the Appendix B. 4x (1−ϵ)
Given a scalar x0 ∈]0, 1 − ζ ] and λϵ,x0 = (1−0ϵ+x )2 , we 0 ( x, y) for any ( x, y) ∈ Xϵ,θ,ζ,η such that x ≥ x0 and have f (λx, λy) ≤ λ fˇX Proposition 5.1.
ϵ,θ,ζ,η
λ ∈ [0, λϵ,x0 ]. The full proof of Proposition 5.1 can be found in Appendix B.1. The scalar λϵ,x0 can be seen as a shrinking factor transforming a feasible solution of the DCMCFenv into a feasible solution of the DCMCF problem that bk x k
y
satisfies the delay Constraints (11) : ∑ a∈ p f ( ca p , caa ) ≤ bk x kp × dk
∀k ∈
K, p ∈ Pk .
Let us introduce additional notation that will be used throughout the remainder of this section: | P| = maxk∈K | Pk | > 1, u = maxa∈ A u a , and b = mink∈K bk . Lemma 5.3.
Given scalars γ > 0 and S > 1, for any k ∈ K, p ∈ Pk and a ∈ p k
such that u a ≥ Sb| Pγk | , we have: post
λγ,S =
4ubγS| P| ≤ λ u a bk γ . 1− c a , (uS| P| + bγ)2 c a S| Pk |
Lemma 5.3 translates this generic shrinking factor into the specific papost
rameters of the DCMCF problem to provide a uniform scaling factor λγ,S
for all paths exceeding a given threshold. The proof, found in Appendix B.2, relies on the monotonicity of the shrinking factor with respect to the demand sizes, path counts, and arc load bounds. Proposition 5.2.
Given a solution of the DCMCFenv problem with objective value
γ̃, there exists a feasible solution of DCMCF with objective value u(| P|−bγ̃1)+bγ̃ γ̃. Proposition 5.2 establishes an ex-post performance guarantee by constructing a feasible DCMCF solution from the relaxation. As detailed in Appendix B.3, the proof filters the relaxed solution by setting path usages below a threshold S∗ to zero, and scales the flow on the remaining paths 32
by the uniform factor established in Lemma 5.3 to ensure the satisfaction of the delay constraints. Lemma 5.4.
Given a DCMCF instance and a scalar α > 1, it is possible to build
in polynomial time a relaxation DCMCFenv with upper bounds u a of variable y a for every a ∈ A and a solution with objective value γ∗ , such that u a ≤ α(∑k∈K bk )γ∗ . Lemma 5.4 ensures that sufficiently tight upper bounds u a on the arc loads can be computed. The proof, provided in Appendix B.4, relies on an iterative process that repeatedly solves the relaxation until the bounding criterion is met. Combining these tight load bounds with the ex-post guarantee from Proposition 5.2 allows us to establish the overall approximation ratio of the algorithm: Theorem 5.2. Given a scalar α > 1, it is possible to build a αβ|K |(| P1|−1)+1 approxk
k∈K b imation of the DCMCF problem in polynomial time, with β = max . min bk k∈K
The proof of Theorem 5.2 is given in Appendix B.5, where we consolidate the previous bounds to extract the final approximation factor.
6
Numerical experiments
In order to assess the relevance of the new relaxations presented in this work, we implemented them with SCIP 10.0 [18] in C++. Tests were conducted with 16 CPUs and 64 GB of RAM. The reformulations of the DCMCF problem described above were implemented. All of them included the Big-M constraints (26) and (27) introduced in Section 4.1, and all of them (except the first one) include additional tightening constraints: • BIG-M : the Big-M formulation introduced in Section 4.1. • CONVEX : the Big-M formulation with Constraints (18) to (25) from the DCMCFenv relaxation.
33
• S : the Big-M formulation, with Constraints (18), (20), and (22) to (25) from the DCMCFenv relaxation, provides a relaxation based on the sϵ,θ function introduced in Section 3.2. • T : the Big-M formulation, with Constraints (18), and (21) to (25) from the DCMCFenv relaxation provides a relaxation based on the tϵ,ζ function introduced in Section 3.3 ; this formulation is comparable to the one presented in [16]. The heuristics and relaxations were tested on two sets of instances. The first set is from the Survivable Network Design Library (SND-Lib, [26]) on which, for every link (u, v) ∈ A, a reverse link (v, u) with capacity c(u,v) was added if it did not exist. Information on these instances is shown in Table 1. The second set includes 126 randomly generated instances (connected Erdös–Rényi graphs, viewed as symmetric directed graphs with symmetric arc costs: c(u,v) = c(v,u) ). These randomly generated instances range from 25 to 200 commodities, 10 to 50 vertices and 30 to 475 arcs. For each demand k ∈ K, a set Pk of the 10 shortest paths, weighted by c1a , was generated through Yen’s algorithm [35]. For each instance, the same delay d = 1.1 × maxk∈K,p∈ Pk ∑ a∈ p c1a was used as the maximum delay
for every commodity k ∈ K. This maximum delay ensures that every path could carry some traffic.
6.1
Heuristics
We first compare the lower bounds obtained by these 3 heuristics H all paths ,
H greedy and Hthreshold defined in Section 5. The heuristic Hthreshold uses the threshold parameter S∗ = 2 − | P2 | + ub|γ̃P| defined in the proof of Proposition 5.2. Figures 5a and 5b show the gaps between these heuristic and the DCMCFenv relaxation, which provides the tightest known relaxation to the delayconstraint problem, as shown in Section 3. Gaps are defined as: gap = γ∗H ∗ the optimal − 1, with γ∗H the objective value of the heuristic and γenv ∗ γenv solution of the DCMCFenv relaxation. In Figure 5b, instances are grouped by the number |K | of commodities and presented as a box plot (the box 34
(a) Heuristics gaps for the SND-Lib in- (b) Heuristics gaps for the random instances stances grouped by|K |
Figure 5: Gaps between the heuristics presented in Section 5 with respect to the CONVEX relaxation. extends from the first quartile to the third quartile of the data, with a line at the median; the whiskers extend from the box to the farthest data point lying within 1.5x the inter-quartile range from the box). By definition, the H greedy (in green) heuristic dominates H all paths (in red). While the H greedy heuristic tends to provide better solutions on smaller instances, its performance seems to deteriorate on larger values of |K | where the Hthreshold heuristic appears to be more efficient (as shown in Figure 5b).
6.2
DCMCF relaxations
The choice of the lower and upper bounds u a , la , ukp , and l kp significantly affects the strength of the resulting relaxations. As described in Section 3.6, bounds can be computed through a closed-formula or a convex optimization problem. In practice, the bounds la kp are set to 0, while la , u a and ukp are computed by solving the corresponding convex-optimization problems. Notice that even when we are considering the bounds related to the BIG-M (resp. S or T) formulation, we use the strongest relaxation (i.e., DCMCFenv ) to compute them. We compare the convex relaxations of the DCMCF problem associated with the formulations BIG-M, S, T and CONVEX described above. As S, T and CONVEX include the constraints of the BIG-M relaxation, they necessarily provide tighter upper bounds for the problem. Similarly, all 35
(a) SND-Lib instances
(b) Randomly-generated instances
Figure 6: Relative gains of the relaxations CONVEX, S and T versus the BIG-M relaxation. constraints from the S and T relaxations are included in the CONVEX relaxation, meaning that the upper bound of the latter is necessarily tighter than the upper bound of the former. Figure 6 provides comparisons of these upper bounds, showing the relative gains of S, T and CONVEX versus the BIG-M relaxation. The relativegain is defined as the difference in objective value between BIG-M and the considered relaxation, divided by the difference between the objective value of the BIG-M relaxation and the best of the Hthreshold , H greedy or H all paths γ∗
−γ∗
∗ is the optimal value heuristics: rel. gainrelax = γ∗BIG− M−γ∗relax where γrelax BIG − M
best H
∗ of the relaxation relax and γbest H is the best lower-bound obtained by the
heuristics described above. The name of the SND-Lib instances is provided in Figure 6a - but the name of the 126 random instances is not shown in Figure 6b. In both figures, instances are ordered by value of the CONVEX relative gain. As proved in Section 3, the CONVEX reformulation indeed dominates both S and T. The absence of domination between the relaxations S and T is consistent with their definition and the fact that functions sϵ,γ and tϵ,ζ dominate each other in different subsets of the feasible region; however, on the randomly-generated instances tested, the S relaxation provides tighter upper bounds than the T relaxation on 123 of the 126 instances tested.
36
6.3
DCMCF exact solving
The DCMCF was solved using a branch-and-bound algorithm. The 4 relaxations presented above (BIG-M, S, T and CONVEX) were implemented and compared. Tables 1 shows, for each SND-lib instance, the respective performances of these formulations: either the solving time if an optimality gap of 0.1% was reached within 1 hour, or the optimality gap if it was above 0.1% after this time limit. For the randomly generated instances, the proportion of random instances solved after a given solving time or, for instances not solved after one hour, the residual gap, are shown in Figure 7. The CONVEX formulation provides a tighter relaxation of the problem than the lighter BIG-M relaxation, at the expense of its solving time. These effects balance each other on instances of the SND-Lib, where the CONVEX formulation outperformed the BIG-M one (either in terms of gap after one hour or solving time if optimality is reached before that time limit) in 11 instances over 19. On the randomly generated instances, however, the lighter BIG-M relaxation proves more efficient on 77 of the 126 instances tested. The S and T formulations provide good trade-offs between tightness and relaxation solving time, allowing them to outperform both the BIG-M (on 12 and 13 instances of the SND-Lib and 72 and 64 randomly-generated instances, respectively). The dominance of the S relaxation, illustrated in Figure 6, does not materialize when solving the exact DCMCF problem in a branch-and-bound scheme: the S relaxation is more efficient than T in 8 of the 19 SND-Lib instances and 72 of the 126 random instances.
7
Conclusion
The Delay-Constrained Multi-Commodity Flow (DCMCF) problem was known to be NP-hard. In this paper, we proved that the problem is strongly NP-hard, even in the case of three commodities that share the same source and destination, and where each commodity is allowed to use every possible path. 37
Instance pdh di-yuan polska nobel-us abilene nobel-germany dfn-bwin atlanta dfn-gwin sun newyork france nobel-eu ta1 geant norway india35 germany50 cost266
|K | 24 22 66 91 132 121 90 210 110 67 240 300 378 396 462 702 595 662 1332
| A| 68 84 36 42 30 52 90 22 47 102 98 90 82 102 72 102 160 88 114
|V | 11 11 12 14 12 17 10 15 11 27 16 25 28 24 22 27 35 50 37
BIG-M (250) (188) 15.9% 29.6% 35.8% 18.1% 7.9% 55.4% 17.6% 35.1% 104% 51% 113.8% 27.4% 97.2% 180.8% 179.7% 128.6% 68.7%
S (960) (462) 16.9% 74.3% 13.5% 16.5% 6.6% 34.5% 16.9% 43% 104% 52.4% 49.3% 26.3% 13.9% 174.1% 158.4% 128.6% 67.3%
T (582) 0.6% 13.5% 58.5% 6.5% 16.3% 9.8% 42.1% 17.5% 35% 104% 49.5% 58.2% 26.9% 9.4% 180.8% 174.8% 128% 64.4%
CONVEX (614) (603) 16% 21.3% 29.4% 17.5% 10.1% 59.2% 16.6% 54.5% 99.6% 50% 50.9% 26.8% 98.8% 180.8% 212.8% 80% 68.6%
Table 1: Branch-and-bound results for the SND-Lib instances We also introduced a new relaxation of the conditional delay constraints and showed that it dominates the relaxations based on disjunctive programming. Moreover, we described a non-trivial approximation algorithm based on the proposed relaxation and established a provable performance guarantee for it. In the process of developing lower-bound heuristics, we proved that the use of certain convex over-estimators does not provide any advantage in the broader context of conditional constraints. In other words, employing such a convex over-estimator when dealing with a constraint of the form xg( x, y) ≤ 0, with x ≥ 0, is equivalent to either fixing x to 0 or imposing the constraint g( x, y) ≤ 0. While this study improves the global understanding of the delay-constrained multi-commodity flow problem, several questions still remain open. For instance, the exact complexity of the problem with a single commodity remains unknown; further improvements to the problem’s relaxations could be investigated in order to develop tractable optimization methods for larger instances. Future work could also focus on developing approximation algo-
38
(a) Performance Graph: solving time
(b) Performance Graph: gap after 1h
Figure 7: Performance graphs for the exact resolution of the DCMCF problem on the randomly generated instances. Left: proportion of instances solved in less than a solving time (for instances solved in less than 1h); right: proportion of instances with a gap below a specified value after 1h. rithms with improved performance guarantees or on refining the analysis of the algorithm presented in this paper.
A
Proof of the DCMCF complexity
A.1
Proof of Lemma 2.1
Proof. The set of all possible paths from s to t is:
{s → ui → v j → t}i∈ I,j∈ J ∪ {s → ui → v j → v1j → · · · → v N j → t }i ∈ I,j∈ J N ∪ {s → v j → v1j → · · · → v N j → t } j∈ J ∪ { s → ui → t }i ∈ I ∪ { s → v j → t } j∈ J ∪ { s → v j → t } j∈ J .
We must prove that commodity k2 cannot follow paths from the first three subsets of this union. For i ∈ I and j ∈ J, the minimum delay of path s → ui → v j → t (obtained if the load of all arcs is zero) is: d s → ui → v j → t =
1 1 1 + + W . mwi + (m − 1)W + 2 wi + 2W + 2 m
1 Using the assumption that wi ≤ W m and W = 4n2 , we can bound the delay
39
of the middle arc (ui , v j ). We have: 1 4mn2 1 m ≥ W = . = wi + 2W W ( 1 + 2m ) 2m + 1 + 2W m Because we assume n ≥ 6 and m ≥ 2, we have n2 ≥ 36 and 2mm+1 ≥ 25 . Therefore wi +12W ≥ 4 × 52 × 36 > 2. Since the delay of this single arc strictly
exceeds 2, we have ds→ui →v j →t > 2 = b2 , ruling out this path for commodity k2 . Similarly, the minimum delay through a path s → ui → v j → v1j →
· · · → vN j → t is strictly greater than 2, since it contains the arc ( ui , v j ), whose zero-load delay we just showed exceeds 2. Notice that the minimum delay through the chain of arcs v j → v1j → · · · → v N j exceeds 1 1 1 1 1 N (n+1)(n−3) = W n2 −2n−3 > W 2 and therefore the delay of a path W
+1
n
4n3
+1
1 → · · · → vN j → t strictly exceeds d L = 2 + 2W , also preventing k2 from using it.
s → ui → v j →
v1j
Finally, for j ∈ J, paths s → v j → v1j → · · · → v N j → t have a minimum delay: ds→v j →v1 →···→v N →t = j
j
1 1 1 + ( N − 1) (n+1)(n−3) + (n+1)(n−3) . 2 W +1 W +2 n
Because n ≥ 6 and W = 4n1 2 , the capacity W
n
(n+1)(n−3) + 1 is strictly less than n
2. As a result, the delay of each of the N − 1 internal arcs strictly exceeds 1 2 2 . Since N = 4n ≥ 144, the total delay is vastly greater than 2. Therefore,
commodity k2 cannot use this path.
A.2
Proof of Lemma 2.2
Proof. From Lemma 2.1, the set of feasible paths for k2 contains n + 2m paths. Let us suppose that one of these paths is not used by k2 (i.e., it carries a load of zero). Because the total size of k2 is b2 = n + 2m, the average load on the remaining paths must be strictly greater than 1 + δ, 40
3 where δ = n+12m = 5n . Consequently, at least one path must carry a load
strictly greater than 1 + δ. We show that the delay of such a path is strictly greater than d2 = 2, which contradicts the feasibility of the flow. • Case 1. Assume that the load through a path {s → ui → t}i∈ I exceeds 1 + δ. The delay is: d s → ui → t ≥
1 1 1 1 + = + . c(s,ui ) − (1 + δ) c(ui ,t) − (1 + δ) mwi + (m − 1)W + 1 − δ 1 − δ
Using wi ≤ W m , we have mwi + ( m − 1)W ≤ W + mW − W = mW = n/3 1 1 = 12n . Thus, because 1− e ≥ 1 + e for e < 1: (2n)2
d s → ui → t ≥
1 1 3 1 + 12n − 5n
+
1 1 3 3 3 1 ≥ (1 − + ) + (1 + ) = 2 + 2 − >2 3 12n 5n 5n 5n 12n 1 − 5n
ensuring that commodity k2 cannot satisfy its delay if a load 1 + δ crosses path s → ui → t. • Case 2. Assume that the load through a path {s → v j → t} j∈ J exceeds 1 + δ. The delay is: ds→v j →t ≥
1 1 1 1 + = + W . c(s,v j ) − (1 + δ) c(v j ,t) − (1 + δ) 1−δ m +1−δ
Using the same reasoning as above, we get: ds→v j →t ≥
1 1 3 3 3 3 3 + ≥ (1 + ) + (1 − 3 + ) = 1 + 2 − 3 > 2 3 3 3 5n 4n 5n 5n 4n 1 − 5n 1 + 4n3 − 5n
ensuring that commodity k2 cannot satisfy its delay if a load 1 + δ crosses path s → v j → t. • Case 3. Assume that the load through a path {s → v N j → t } j∈ J exceeds 1 + δ. The delay is: ds→v N →t ≥ j
1 1 1 1 . + = + (n+1)(n−3) c(s,v N ) − (1 + δ) c(v N ,t) − (1 + δ) 1−δ W +1−δ j
j
41
n
Following the same reasoning as the other cases, we get: ds→v N →t ≥ j
1 1 + 3 ( n + 1 )( n −3) 1 − 5n − 3 1+ 3
5n
4n
≥ (1 +
3 (n + 1)(n − 3) 3 3 (n + 1)(n − 3) ) + (1 − + ) = 2+2 − 5n 4n3 5n 5n 4n3
> 2. Therefore, commodity k2 cannot route more than 1 + δ on any of these paths. Since the total load is n + 2m, it must use each path in {s → ui → t }i ∈ I ∪ { s → v j → t } j∈ J ∪ { s → v N j → t } j∈ J .
A.3
Proof of Lemma 2.3
1 Proof. Let us consider the delay of arc (ui , t). Using the inequality 1− e ≥
1 + e for e < 1 (with a strict inequality if e ̸= 0 and equality if e = 0), we get: d(ui ,t) =
1 1 1 = = c(ui ,t) − y(ui ,t) 2 − ( 1 + ϵi ) 1 − ϵi
=⇒
d(ui ,t) > 1 + ϵi
if
ϵi ̸ = 0
(i.e., if i ∈ Q I )
d(ui ,t) = 1
if
ϵi = 0
(i.e., if i ∈ I \ Q
Using the same inequality on the delay of the arc (s, ui ) we get: d(s,ui ) =
1 1 = ≥ 1 + y(s,ui ) − (mwi + (m − 1)W + 1). c(s,ui ) − y(s,ui ) mwi + (m − 1)W + 2 − y(s,ui )
Because commodity k2 must use the path s → ui → t, the total delay of this path is less than or equal to d2 = 2. Therefore: • if i ∈ Q I : d2 = 2 ≥ d(s,ui ) + d(ui ,t) > 1 + ϵi + 1 + y(s,ui ) − (mwi + (m − 1)W + 1) which implies that: y(s,ui ) < mwi + (m − 1)W + 1 − ϵi
∀i ∈ Q I .
• if i ∈ I \ Q I , we have d(ui ,t) = 1 and therefore d(s,ui ) ≤ 1, which leads to: y(s,ui ) ≤ mwi + (m − 1)W + 1 42
∀i ∈ I \ Q I .
A.4
Proof of Lemma 2.4
Proof. The reasoning is identical to the proof of Lemma 2.3. We apply the 1 inequality 1− e ≥ 1 + e (valid for e < 1, with a strict inequality when e ̸ = 0
and equality for e = 0) to the delays of the arcs forming the 2-hop paths. Consider the path s → v j → t. The delay of the first arc is d(s,v j ) = 1 c(s,v ) −y(s,v ) j
j
= 2−(11+ϵj ) . This gives d(s,v j ) > 1 + ϵ j if j ∈ Q J , and d(s,v j ) = 1
otherwise. For the second arc, applying the same inequality gives: 1 1 d(v j ,t) = ≥ 1 + y(v j ,t) − = W c(v j ,t) − y(v j ,t) m + 2 − y(v j ,t)
W +1 . m
Because commodity k2 must respect the maximum delay constraint d2 = 2 ≥ d(s,v j ) + d(v j ,t) on this path, we get: • For j ∈ Q J , the strict inequality on the first arc implies 2 > 1 + ϵ j + W 1 + y(v j ,t) − W m + 1 , which leads to y(v j ,t) < m + 1 − ϵ j . • For j ∈ J \ Q J , the equality on the first arc implies 2 ≥ 1 + 1 + y(v j ,t) − W + 1 , leading to y(v j ,t) ≤ W m m + 1. The same reasoning applies to the path s → v N j → t. The delay of the first arc d(s,v N ) = c j
(s,v N ) j
1 −y(s,v N ) j
= 2−(11+ϵ′ ) is strictly greater than 1 + ϵ′j for j
j ∈ Q′J and equals 1 if j ∈ J \ Q′J . The delay of the second arc satisfies: 1 1 d(v N ,t) = = (n+1)(n−3) j c(v N ,t) − y(v N ,t) W +2−y j
j
n
(n + 1)(n − 3) ≥ 1 + y(v N ,t) − W +1 . j n
(v N j ,t )
Enforcing the maximum delay of 2 across the entire path guarantees that y(v N ,t) < W j
W
(n+1)(n−3) + 1 − ϵ′j for any j ∈ Q′J , and less than or equal to n
(n+1)(n−3) + 1 otherwise. n
43
A.5
Proof of Lemma 2.5
Proof. We will consider the sum of the loads of all arcs exiting s and entering t to show that successfully routing a throughput of γ = 1 requires Q I ∪ Q J ∪ Q′J = ∅. From Lemmas 2.3 and 2.4, and the definitions of the ϵ variables, we can bound the load on each arc of the 2-hop paths: • For a given i ∈ I, the upper bounds on the arc loads are y(s,ui ) ≤ mwi + (m − 1)W + 1 − ϵi and y(ui ,t) ≤ 1 + ϵi . The first bound is strict if i ∈ Q I . Summing over i ∈ I gives:
∑(y(s,u ) + y(u ,t) ) ≤ mW + n(m − 1)W + 2n = bL + bH + 2n i
i∈ I
i
with this inequality being strict if Q I ̸= ∅. • For a given j ∈ J, the upper bounds on the arc loads are y(s,v j ) ≤ 1 + ϵ j and y(v j ,t) ≤ W m + 1 − ϵ j . The second bound is strict if j ∈ Q J . Summing over j ∈ J gives:
∑(y(s,v ) + y(v ,t) ) ≤ W + 2m = bL + 2m j
j∈ J
j
with this inequality being strict if Q J ̸= ∅. • For a given j ∈ J, the upper bounds on the arc loads are y(s,v N ) ≤ 1 + ϵ′j j
and y(v N ,t) ≤ W j
(n+1)(n−3) + 1 − ϵ′j . The second bound is strict if j ∈ Q′J . n
Summing over j ∈ J gives:
∑(y(s,v ) + y(v ,t) ) ≤ mW j∈ J
N j
N j
(n + 1)(n − 3) + 2m = b H + 2m n
with this inequality being strict if Q′J ̸= ∅. Because there are no arcs exiting s or entering t other than those analyzed above, we can sum them to obtain the global bound on the network’s entry
44
and exit flows:
∑ ya + ∑− ya ≤ 2(bL + bH + b2 )
a∈δ+ (s)
a∈δ (t)
with a strict inequality if Q I ∪ Q J ∪ Q′J ̸= ∅. To successfully route the complete demands for all three commodities, the total flow leaving s and entering t must be exactly 2(bL + b H + b2 ). Therefore, we must have Q I ∪ Q J ∪ Q′J = ∅, meaning all ϵi , ϵ j , and ϵ′j terms are exactly zero. It also follows that all the upper bounds on the arc loads hold as strict equalities. We can finally deduce that y(s,ui ) = mwi + (m − 1)W + 1, y(v j ,t) = W = W (n+1)(n n−3) + 1, y(ui ,t) = 1, y(s,v j ) = 1, and y(s,v N ) = 1. We m + 1, y(v N j ,t ) j
also conclude that the delay on each of these arcs is exactly equal to 1.
A.6
Proof of Lemma 2.6
Proof. We have observed that k L cannot cross arcs in {(ui , t)}i∈ I , {(s, v j )} j∈ J , or {(s, v N j )} j∈ J . Therefore, it cannot use paths in { s → ui → t }i ∈ I ∪ { s → 1 N v j → t } j∈ J ∪ { s → v N j → t } j∈ J ∪ { s → v j → v j → · · · → v j → t } j∈ J .
Moreover, as established in the proof of Lemma 2.1, the delay on paths involving the arc chains v j → v1j → · · · → v N j is strictly greater than 1 , which exceeds the delay limit for k L . d L = 2 + 2W
The only remaining feasible paths for k L are therefore those in {s → ui → v j → t}i∈ I,j∈ J .
A.7
Proof of Lemma 2.7
Proof. From Lemma 2.6, commodity k L enters vertex t exclusively through the set of arcs {(v j , t)} j∈ J . Equation (8) establishes that the total load on each of these arcs is W m + 1. Because commodity k 2 routes exactly 1 unit of flow on each arc (v j , t), the remaining flow on these arcs must belong to commodity k L . Therefore, the load of k L on each arc (v j , t) is exactly W m. 45
Summing over all m arcs confirms that the total volume routed matches the demand bL = W.
A.8
Proof of Lemma 2.8
Proof. Equation (9) establishes that the total load on each arc (v N j , t ) is (n+1)(n−3) + 1. Knowing that 1 unit of flow is already routed by commodn ity k2 on each arc (v N j , t ), the remaining flow on these arcs must belong to (n+1)(n−3) commodity k H . Thus, the load of k H on each arc (v N . j , t ) is W n
W
By the conservation of flow, because commodity k H only enters t through these arcs and must cross the entire arc chain to reach them, this result extends to all arcs in the chain: the entry arcs {(v j , v1j )} j∈ J , the internal arcs
{(vlj , vlj+1 )} j∈ J,l ∈[1,N −1] , and the exit arcs {(v N j , t )} j∈ J . Finally, substituting these loads back into the delay functions confirms that the delay on each of these arcs is exactly 1.
A.9
Proof of Lemma 2.9
Proof. From Lemma 2.1, commodity k2 never crosses the arcs (ui , v j ). These arcs are therefore exclusively used by commodities k L and k H . From Lemma 2.5, we know that the delays of the entry and exit arcs are d(s,ui ) = 1 and d(v j ,t) = 1. Lemma 2.8 establishes that the total delay of the sub-path v j → v1j →
· · · → vN j → t used by commodity k H is N + 1. Because the maximum 1 delay limit for commodity k H is d H = N + 2 + W , any arc (ui , v j ) traversed by k H must satisfy: d(s,ui ) + d(ui ,v j ) + ( N + 1) ≤ d H =⇒ 1 + d(ui ,v j ) + N + 1 ≤ N + 2 + Since d(ui ,v j ) = c
1
(ui ,v j ) − y(ui ,v j )
= wi +2W1−y
(ui ,v j )
1 1 =⇒ d(ui ,v j ) ≤ . W W
, this delay constraint imposes
the upper bound on the load y(ui ,v j ) ≤ wi + W for any arc (ui , v j ) traversed by k H . 46
1 Similarly, the maximum delay limit for commodity k L is d L = 2 + 2W .
Any arc (ui , v j ) traversed by k L must satisfy: d(s,ui ) + d(ui ,v j ) + d(v j ,t) ≤ d L =⇒ 1 + d(ui ,v j ) + 1 ≤ 2 +
1 1 =⇒ d(ui ,v j ) ≤ . 2W 2W
This stricter delay constraint imposes the tighter upper bound y(ui ,v j ) ≤ wi for any arc (ui , v j ) traversed by k L . By flow conservation, the total flow exiting node ui equals the total flow entering that node for any i ∈ I. Lemma 2.5 shows that the load entering ui is y(s,ui ) = mwi + (m − 1)W + 1, and the load exiting on arc (ui , t) is y(ui ,t) = 1. Therefore, the total load distributed across the m outgoing arcs
{(ui , v j )} j∈ J is:
∑ y(u ,v ) = y(s,u ) − 1 = mwi + (m − 1)W j∈ J
i
j
i
We deduce that at least m − 1 arcs must carry a load strictly greater than wi . If this were not the case, at least two arcs would carry a load of at most wi , and the remaining m − 2 arcs would carry a maximum of wi + W. The total flow would then be bounded by 2wi + (m − 2)(wi + W ) = mwi + (m − 2)W, which is strictly less than the flow mwi + (m − 1)W exiting node ui . Because commodity k L requires y(ui ,v j ) ≤ wi , it can cross at most one arc
(ui , v j ) for any given i ∈ I, meaning it can route a maximum volume of wi from that object node. Given that the total demand for commodity k L is bL = W = ∑i∈ I wi , it must maximize its allowed flow across all object nodes {ui }i∈ I . Thus, k L must use exactly one arc (ui , v j ) per object i ∈ I and route exactly wi units of flow across it. Consequently, the remaining m − 1 arcs exiting each ui must carry exactly wi + W of commodity k H and exhibit a 1 delay of exactly W .
47
A.10
Proof of Lemma 2.10
Proof. Using the loads y(s,v j ) = 1, y(v j ,t) = W m + 1, and y(v j ,v1 ) = W j
(n+1)(n−3) n
for any j ∈ J established in Lemmas 2.5 and 2.8 we have, by flow conservation at node v j : y(s,v j ) + ∑ y(ui ,v j ) = y(v j ,t) + y(v j ,v1 ) j
i∈ I
W (n + 1)(n − 3) +1 +W m n i∈ I 2 W (n + 1)(n − 3) 3 n2 − 2n − 3 n − 2n =W + =W = W ( n − 2) ∑ y(ui ,vj ) = m + W n n n n i∈ I
1 + ∑ y(ui ,v j ) =
∑ y(u ,v ) = ∑ wi + W (n − 3). i∈ I
i
j
i∈ I
The only commodities crossing arcs (ui , v j ) are k L and k H . Let l be the number of arcs entering v j that carry commodity k L ; from Lemma 2.9, commodity k H is carried by the remaining n − l arcs. For every i ∈ I, the load of arc (ui , v j ) is exactly wi if it is crossed by commodity k L , and exactly wi + W if it is crossed by commodity k H . The total load on the n arcs (ui , v j ) can be expressed as:
∑ y(u ,v ) = i∈ I
i
j
∑
arcs carrying k L
wi +
∑
arcs carrying k H
(wi + W ) = ∑ wi + (n − l )W. i∈ I
Hence, we have ∑i∈ I wi + W (n − 3) = ∑i∈ I wi + W (n − l ), which implies l = 3. Therefore, commodity k L is carried by exactly 3 arcs in {(ui , v j )}i∈ I for every j ∈ J.
A.11
Proof of Proposition 2.2
Proof. Lemma 2.9 establishes that for every i ∈ I, commodity k L is routed through exactly one arc (ui , v j ). For each j ∈ J, let Tj ⊂ I denote the subset of objects i for which commodity k L uses the arc (ui , v j ). Lemma 2.10 proves that each subset Tj contains exactly 3 elements. Because every object i ∈ I 48
is assigned to exactly one subset, the collection { Tj } j∈ J forms a partition of I into triplets. By flow conservation, the volume of commodity k L entering node v j must equal the volume exiting it. From Lemma 2.9, the load of k L entering v j from the object nodes is ∑i∈Tj wi . From Lemma 2.7, the load of k L exiting W v j on arc (v j , t) is W m . Therefore, we have: ∑i ∈ Tj wi = m
∀ j ∈ J. We can conclude that the partition { Tj } j∈ J is a valid solution for the 3-Partition problem defined by the multiset {wi }i∈ I .
B
Proof of the perfomance guarantee of Hthreshold
B.1
Proof of Proposition 5.1
Proof. Since fˇXϵ,θ,ζ,η ( x, y) ≥ sϵ,θ ( x, y), if f (λx, λy) ≤ λsϵ,θ ( x, y) holds, then f (λx, λy) ≤ λ fˇX ( x, y) is also valid. ϵ,θ,ζ,η
If λ = 0, the inequality in the proposition holds trivially. Let us then assume that λ > 0. Inequality f (λx, λy) ≤ λsϵ,θ ( x, y) is then equivalent to: 1 − s (xx,y) ϵ,θ = λ≤ y
x
1−
x
1− θ − 1−
x y− x −θ 1− ϵ − θ
y
=
(θ + x )(1 − ϵ) − θy = qϵ,θ ( x, y). y (1 − ϵ + x ) − y2
(36)
For a given y ∈]η, 1 − ϵ], the function qϵ,θ defined above is increasing in x ∈ [0, min(y − θ, 1 − ζ )] since its derivative is given by
(1−ϵ−y)(1−ϵ−θ ) . Simy (1− ϵ + x − y )2
ilarly, qϵ,θ is increasing with respect to θ for any θ satisfying (13). Therefore, given an x0 ∈ [0, 1 − ζ ], f (λx, λy) ≤ λ fˇ( x, y) holds for any x ≥ x0 and any λ ≤ qϵ,0 ( x0 , y). x (1− ϵ )
Moreover, qϵ,0 ( x0 , y) = y(1−0ϵ+x )−y2 attains its lower bound when y∗ = 0
4x (1−ϵ) 1− ϵ + x0 , with a value of (1−0ϵ+x )2 . 2 0
satisfies (36).
4x (1−ϵ)
Hence λϵ,x0 = qϵ,0 ( x0 , y∗ ) = (1−0ϵ+x )2 0
49
B.2
Proof of Lemma 5.3
Proof. First, observe that λ
1− ucaa ,
bk γ c a S| Pk |
= 4
bk γ u a c a S| Pk | c a k ( ucaa + b γk )2 c a S| P |
k
k
derivative of this expression with respect to bk , ∂b∂ k
λ
is positive for bk ≤
u a S| Pk |
bk and λ
u a S| P | ≥ (4bγ with b = mink∈K bk . uS| Pk |+bγ)2
γ
k
a S| P | = (u4bSγ| Puk |+ . The b k γ )2 a !
bk γ
. Therefore, if u a ≥ S| Pk | , λ
1− uc aa ,
bk γ c a S| Pk |
a
increases with
k
k 1− ucaa , b γk c a S| P |
k
S| P | Similarly, the derivative of (u4bγS| Puka |+ with respect to | Pk | is negative bγ)2 a
k
bγ . Notice that, under the assumption u a ≥ Sb| Pγk | , it follows that if | Pk | ≥ Su a k
k
S| P | S| P | u a ≥ Sbγ . Therefore, (u4bγS| Puka |+ decreases with | Pk | and (u4bγS| Puka |+ ≥ | Pk | bγ)2 bγ)2 a
a
4bγ u a S| P| with | P| = maxk∈K | Pk |. (u a S| P|+bγ)2 a S| P| Finally, the derivative of (u4bγS| Pu|+ with respect to u a is negative if u a ≥ bγ)2 a 4bγ u a S| P| bk γ bγ a S| P| . Hence, if u a ≥ S| Pk | , (u S| P|+bγ)2 decreases with u a and (u4bγS| Pu|+ ≥ S| P| bγ)2 a a 4bγ u S| P| 4ubγS| P| with u = maxa∈ A u a , and we get λ ua bk γ ≥ (uS| P|+bγ)2 . (uS| P|+bγ)2 1− c a , k c a S| P |
B.3
Proof of Proposition 5.2
Proof. Let us consider a scalar S > 1 and a solution of DCMCFenv ; variable values of this solution are denoted by a tilde ( ˜· ). We define, for every commodity k ∈ K, the set of paths QkS = { p ∈ Pk : x̃ kp ≥ S|γ̃Pk | }.
Let us construct a feasible solution (x̄ kp , ȳ a , γ̄) of DCMCF as follows: x̄ kp = ȳ a =
λ post x̃ k
if
p ∈ QkS
0
if
p ∈ Pk \ QkS
∑
bk x̄ kp
γ̃,S
p
∀k ∈ K, p ∈ Pk ∀a ∈ A
k ∈K,p∋ a
γ̄ = min ∑ x̄ kp . k∈K
p∈ Pk
post
post
If p ∈ QkS , then x̄ kp = λγ̃,S x̃ kp , and ȳ a ≤ λγ̃,S ỹ a for a ∈ A. Observe also k
that, for such a path p, x̃ kp ≥ S|γ̃Pk | implies that u a ≥ ỹ a ≥ bk x̃ kp ≥ Sb| Pγ̃k | for 50
k
k
a S | P |− b γ ) , = 4γua(Su| PS||(Puk |+ b k γ )3
k 1− uc aa , b γk c a S| P |
any a ∈ p. One can then apply Lemma 5.3 and Proposition 5.1 for every k ∈ K and p ∈ QkS : post
bk x̄ kp
∑ ca − ȳa ≤ ∑
bk λγ̃,S x̃ kp
post a∈ p c a − λγ̃,S ỹ a
a∈ p
post
≤ λγ̃,S
∑ fˇX −
k k k c a u a , l a p , c a −b u p , l a ca ca ca ca
a∈ p
(
bk x̃ kp ỹ a post , ) ≤ λγ̃,S bk dk x̃ kp = bk dk x̄ kp ca ca
proving that constraints (6) are satisfied for all k ∈ K and p ∈ QkS . If p ∈ Pk \ QkS then x̄ kp = 0 and the constraint is trivially satisfied. It is straightforward to check that all other constraints of the DCMCF problem are satisfied, so the constructed solution is feasible. Since S > 1, QkS contains at least one path. Consequently, the following lower bound holds for any k ∈ K: ∑ p∈Qk x̃ kp ≥ S
S| Pk |−(| Pk |−1) γ̃, implying that S| Pk |
k k post S | P | − (| P | − 1) γ̃ k S| P |
γ̄ = min ∑ x̄ kp = min ∑ λγ̃,S x̃ kp ≥ min λγ̃,S post
k∈K
k∈K
p∈ Pk
k∈K
p∈ QkS
k S| Pk |−(| Pk |−1) Pk |−1) ≤ 0 on R+ ; therefore S| P |−(| ≥ S| Pk | S| Pk | post S| P|−(| P|−1) S| P|−(| P|−1) 4bγ̃ u S| P| S| P|−(| P|−1) and γ̄ ≥ λγ̃,S γ̃ = (uS γ̃. S| P| S| P| S| P| | P|+bγ̃)2 b γ̃ 2 Finally, let S∗ = 2 − | P| + u| P| > 1 be the value of S maximizing the
Observe that ∂| P∂ k |
lower bound of γ̄. One can then deduce that: γ̄ ≥
4bγ̃ u S∗ | P|
S∗ | P| − (| P| − 1)
(uS∗ | P| + bγ̃)2
S∗ | P|
γ̃ =
4bγ̃ u(S∗ | P| − (| P| − 1))
(uS∗ | P| + bγ̃)2
4bγ̃ u (2 − | P2 | + ub|γ̃P| )| P| − (| P| − 1) b γ̃ = γ̃ = 2 u(| P| − bγ̃ 2 u(2 − | P| + u| P| )| P| + bγ̃
This shows that, given the solution of the DCMCFenv problem with objective value γ̃, there exists a solution of DCMCF with objective value γ̄ ≥ u(| P|−bγ̃1)+bγ̃ γ̃.
B.4
Proof of Lemma 5.4
Proof. Let us consider an instance of DCMCF and a scalar α > 1. We denote by u0a the upper bound of variable y a for a ∈ A. Such bounds can be derived analytically as described in Section 3.6. Upper bounds of variables x kp can similarly be computed for every k ∈ K and p ∈ Pk , and lower bounds la and la kp can be set to zero.
51
n } n ∈N We can now iteratively generate a sequence of relaxations { DCMCF env n , with upper bounds una for each as follows. Given the relaxation DCMCF env
arc a ∈ A and optimal objective value γn∗ , either one of the two following conditions is met: 1. Direct Success: The relaxation immediately satisfies the desired propn erty: for every arc a ∈ A, the optimal objective value of DCMCF env
and the upper bound of every arc a satisfy una ≤ α(∑k∈K bk )γn∗ . 2. Bounds Improvement: The relaxation does not satisfy the desired propn +1 erty, but bounds can be improved: a new problem DCMCF env with, n + 1 n k for every arc a ∈ A, a new upper bound u a = min u a , (∑k∈K b )γn∗ is created and solved. n +1 The new problem DCMCF env constructed in the latter case remains a
relaxation of DCMCF, since (∑k∈K bk )γn∗ is a valid upper bound on the load of each arc a ∈ A. If this process is run for 1 + | A| iterations and the condition is still not satisfied (i.e., no direct success), then there exists at least one arc a for which the upper bound has been updated twice. In other words, we have una > α(∑k∈K bk )γn∗ and una +l > α(∑k∈K bk )γn∗+l for some a ∈ A, and some l ≤ 1 + | A|. Hence, the following inequalities hold: α(∑k∈K bk )γn∗+l < una +l ≤ una +1 ≤ (∑k∈K bk )γn∗ , implying that
γn∗+l γn∗
≤ α1 . Since the γn∗ values cannot fall below the lower bound γlow defined in (35), the iterative process must terminate and generate a relaxation of DCMCF satisfies the l envthat m γ0∗ required conditions within a maximum of (| A| + 1) logα γlow iterations. a∈ A a Since γ0∗ is less than the trivial upper bound ∑ , the number of iterations bk ∑
c
k∈K
is polynomially bounded in the size of the instance, ending the proof.
B.5
Proof of Theorem 5.2
Proof. Given a DCMCF instance and any constant α > 1, Lemma 5.4 ensures that one can construct a relaxation DCMCFenv with optimal value γ∗ such that, for every a ∈ A, u a ≤ α(∑k∈K bk )γ∗ . 52
Proposition 5.2 shows that there exists a solution of DCMCF with ∗
∗
objective value γ̄∗ ≥ u(| P|−bγ1)+bγ∗ γ∗ . Since u(| P|−bγ1)+bγ∗ γ∗ decreases with u = maxa∈ A u a ≤ α(∑k∈K bk )γ∗ ≤ α|K |γ∗ maxk∈K bk , we have:
γ̄∗ ≥
bγ∗ 1 1 bγ∗ ∗ γ∗ ≥ γ∗ = γ ≥ γ∗ maxk∈K bk u(| P| − 1) + bγ∗ αβ | K |(| P | − 1) + 1 α|K |γ∗ (| P| − 1) maxk∈K bk + bγ∗ α |K |(| P| − 1) + 1 b
ending the proof.
References [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts, 1988. [2] P.-O. Bauguion, W. Ben-Ameur, and E. Gourdin. Efficient algorithms for the maximum concurrent flow problem. Networks, 65 (1):56–67, 2015. doi: https://doi.org/10.1002/net.21572. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21572. [3] S. Beker, D. Kofman, and N. Puech. Off-line mpls layout design and reconfiguration: Reducing complexity under dynamic traffic conditions. In International Network Optimization Conference (INOC), pages 61–66, 2003. [4] W. Ben-Ameur and A. Ouorou. Mathematical models of the delay constrained routing problem. Algorithmic Operations Research, 1(2):94–103, 2006. [5] G. Beraud-Sudreau, L. Létocart, Y. Magnouche, and S. Martin. On the multi-commodity flow with convex objective function: Column-generation approaches. Networks, 2026. [6] D. Bienstock. Potential function methods for approximatively solving linear programs: theory and practice. Technical report, CORE Lecture Series Monograph, 2001. [7] D. Bienstock and O. Raskina. Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem. Mathematical Programming, Ser. B, 91:479–492, 2002. [8] P. Bonami, D. Mazauric, and Y. Vaxès. Maximum flow under proportional delay constraint. Theoretical Computer Science, 689:58–66, 2017. [9] X. Dong, W. Li, X. Zhou, K. Li, and H. Qi. Tina: A fair inter-datacenter transmission mechanism with deadline guarantee. In IEEE INFOCOM 2020IEEE Conference on Computer Communications, pages 2017–2025. IEEE, 2020.
53
[10] C. Duhamel and A. Mahul. An augmented lagrangean approach for the qos constrained routing problem. Technical report, LIMOS, UMR6158-CNRS, 2007. [11] L. Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math., 13(4):505–520, 2000. [12] B. Fortz, L. Gouveia, and M. Joyce-Moniz. Models for the piecewise linear unsplittable multicommodity flow problems. European Journal of Operational Research, 261(1):30–42, 2017. [13] M. R. Garey and D. S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM journal on Computing, 4(4):397–411, 1975. [14] N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630–652, 2007. [15] H. Hijazi, P. Bonami, and A. Ouorou. An outer-inner approximation for separable minlps. LIF, 2010. [16] H. Hijazi, P. Bonami, G. Cornuéjols, and A. Ouorou. Mixed-integer nonlinear programs featuring “on/off” constraints. Computational Optimization and Applications, 52(2):537–558, 2012. [17] H. Hijazi, P. Bonami, and A. Ouorou. Robust delay-constrained routing in telecommunications. Annals of Operations Research, 206(1):163–181, 2013. [18] C. Hojny, M. Besançon, K. Bestuzheva, S. Borst, J. Dionísio, J. Ehls, L. Eifler, M. Ghannam, A. Gleixner, A. Göß, et al. The scip optimization suite 10.0. arXiv preprint arXiv:2511.18580, 2025. [19] G. Karakostas. Faster approximation schemes for fractional multicommodity flow problems. ACM Transactions on Algorithms, 4(1):1–17, 2008. [20] L. Kleinrock. Theory, volume 1, queueing systems. Wiley-interscience, 1975. [21] T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM, 46:215–245, 1999. [22] M. Locatelli. Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes. Journal of Global Optimization, 66(4):629–668, 2016. [23] M. Locatelli. Convex envelopes of bivariate functions through the solution of kkt systems. Journal of global optimization, 72(2):277–303, 2018. [24] D. Matula and F. Shahrokhi. The maximum concurrent flow problem and sparsest cuts. Technical report, Southern Methodist Univ. Dallas, 1986.
54
[25] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems. Mathematical programming, 10(1):147–175, 1976. [26] S. Orlowski, R. Wessaly, M. Pioro, and A. Tomaszewski. Sndlib 1.0—survivable network design library. Networks: An International Journal, 55(3):276–286, 2010. [27] A. Ouorou, P. Mahey, and J.-P. Vial. A survey of algorithms for convex multicommodity flow problems. Management science, 46(1):126–147, 2000. [28] D. Papadimitriou and B. C. Vũ. An augmented lagrangian method for nonconvex composite optimization problems with nonlinear constraints. Optimization and Engineering, 25(4):1921–1990, 2024. [29] M. Pióro and D. Medhi. Routing, flow, and capacity design in communication and computer networks. Morgan Kaufmann, 2004. ISBN 978-0-12-557189-0. [30] H. D. Sherali and A. Alameddine. An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes. Annals of Operations Research, 25(1):197–209, 1990. [31] D. Shmoys. Cut problems and their application to divide-and-conquer. In D. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 192–235. PWS Publishing Company, 1997. [32] J. Truffot, C. Duhamel, and P. Mahey. k-splittable delay constrained routing problem: A branch-and-price approach. Networks, 55(1):33–45, 2010. [33] N. Wang, K. H. Ho, G. Pavlou, and M. Howarth. An overview of routing optimization for internet traffic engineering. IEEE Communications Surveys & Tutorials, 10(1):36–56, 2008. [34] H.-H. Yen and F.-S. Lin. Near-optimal delay constrained routing in virtual circuit networks. In Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No. 01CH37213), volume 2, pages 750–756. IEEE, 2001. [35] J. Y. Yen. Finding the k shortest loopless paths in a network. management Science, 17(11):712–716, 1971.
55