Multi-commodity flow problem

The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. Given a flow network G ( V , E ) {displaystyle ,G(V,E)} , where edge ( u , v ) ∈ E {displaystyle (u,v)in E} has capacity c ( u , v ) {displaystyle ,c(u,v)} . There are k {displaystyle ,k} commodities K 1 , K 2 , … , K k {displaystyle K_{1},K_{2},dots ,K_{k}} , defined by K i = ( s i , t i , d i ) {displaystyle ,K_{i}=(s_{i},t_{i},d_{i})} , where s i {displaystyle ,s_{i}} and t i {displaystyle ,t_{i}} is the source and sink of commodity i {displaystyle ,i} , and d i {displaystyle ,d_{i}} is its demand. The variable f i ( u , v ) {displaystyle ,f_{i}(u,v)} defines the fraction of flow i {displaystyle ,i} along edge ( u , v ) {displaystyle ,(u,v)} , where f i ( u , v ) ∈ [ 0 , 1 ] {displaystyle ,f_{i}(u,v)in } in case the flow can be split among multiple paths, and f i ( u , v ) ∈ { 0 , 1 } {displaystyle ,f_{i}(u,v)in {0,1}} otherwise (i.e. 'single path routing'). Find an assignment of all flow variables which satisfies the following four constraints: (1) Link capacity: The sum of all flows routed over a link does not exceed its capacity. (2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node u {displaystyle u} is the same that exits the node. (3) Flow conservation at the source: A flow must exit its source node completely. (4) Flow conservation at the destination: A flow must enter its sink node completely. Load balancing is the attempt to route flows such that the utilization U ( u , v ) {displaystyle U(u,v)} of all links ( u , v ) ∈ E {displaystyle (u,v)in E} is even, where The problem can be solved e.g. by minimizing ∑ u , v ∈ V ( U ( u , v ) ) 2 {displaystyle sum _{u,vin V}(U(u,v))^{2}} . A common linearization of this problem is the minimization of the maximum utilization U m a x {displaystyle U_{max}} , where In the minimum cost multi-commodity flow problem, there is a cost a ( u , v ) ⋅ f ( u , v ) {displaystyle a(u,v)cdot f(u,v)} for sending a flow on ( u , v ) {displaystyle ,(u,v)} . You then need to minimize