In the minimum-cost multi-commodity-flow problem, we are given directed graph G = (V, E) in which each edge (u, ) E has a nonnegative

In the minimum-cost multi-commodity-flow problem, we are given directed graph G = (V, E) in which each edge (u, ν) ∈ E has a nonnegative capacity c(u, ν) ≥ 0 and a cost a (u, ν). As in the multi-commodity-flow problem, we are given k different commodities, K₁, K₂, . . . ,K_k, where we specify commodity i by the triple K_i = (s_i, t_i, d_i). We define the flow f_i for commodity i and the aggregate flow f_uν on edge (u, ν) as in the multi-commodity-flow problem. A feasible flow is one in which the aggregate flow on each edge (u, ν) is no more than the capacity of edge (u, ν). The cost of a flow is ∑_{u, ν ∈ V} a(u, ν) f_uν, and the goal is to find the feasible flow of minimum cost. Express this problem as a linear program.