In the minimum-cost multi-commodity-flow problem, we are given directed graph G = (V, E) in which each
Question:
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, K1, K2, . . . ,Kk, where we specify commodity i by the triple Ki = (si, ti, di). We define the flow fi for commodity i and the aggregate flow fuν 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, ν) fuν, and the goal is to find the feasible flow of minimum cost. Express this problem as a linear program.
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest