{
  "id": "multi-commodity-flow-problem-781700-123f39f1d6d08b4d",
  "slug": "multi-commodity-flow-problem",
  "title": "Multi-commodity flow problem",
  "qid": "Q6934437",
  "lead": "The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.",
  "body": "The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. ==Definition== Given a flow network \\,G(V,E) , where edge (u,v) \\in E has capacity \\,c(u,v) . There are \\,k commodities K_1,K_2,\\dots,K_k , defined by \\,K_i=(s_i,t_i,d_i) , where \\,s_i and \\,t_i is the source and sink of commodity \\,i , and \\,d_i is its demand. The variable \\,f_i(u,v) defines the fraction of flow \\,i along edge \\,(u,v) , where \\,f_i(u,v) \\in [0,1] in case the flow can be split among multiple paths, and \\,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. \\forall (u,v)\\in E:\\,\\sum_{i=1}^{k} f_i(u,v)\\cdot d_i \\leq c(u,v) (2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node u is the same that exits the node. \\forall i\\in\\{1,\\ldots,k\\}:\\,\\sum_{(u,w) \\in E} f_i(u,w) - \\sum_{(w,u) \\in E} f_i(w,u) = 0 \\quad \\mathrm{when} \\quad u \\neq s_i, t_i (3) Flow conservation at the source: A flow must exit its source node completely. \\forall i\\in\\{1,\\ldots,k\\}:\\,\\sum_{(s_i,w) \\in E} f_i(s_i,w) - \\sum_{(w,s_i) \\in E} f_i(w,s_i) = 1 (4) Flow conservation at the destination: A flow must enter its sink node completely. \\forall i\\in\\{1,\\ldots,k\\}: \\,\\sum_{(w,t_i) \\in E} f_i(w,t_i) - \\sum_{(t_i,w) \\in E} f_i(t_i,w) = 1 ==Corresponding optimization problems== Load balancing is the attempt to route flows such that the utilization U(u,v) of all links (u,v)\\in E is even, where U(u,v)=\\frac{\\sum_{i=1}^{k} f_i(u,v)\\cdot d_i}{c(u,v)} The problem can be solved e.g. by minimizing \\sum_{u,v\\in V} (U(u,v))^2 . A common linearization of this problem is the minimization of the maximum utilization U_{max} , where \\forall (u,v)\\in E:\\, U_{max} \\geq U(u,v) In the minimum cost multi-commodity flow problem, there is a cost a(u,v) \\cdot f(u,v) for sending a flow on \\,(u,v) . You then need to minimize \\sum_{(u,v) \\in E} \\left( a(u,v) \\sum_{i=1}^{k} f_i(u,v)\\cdot d_i \\right) In the maximum multi-commodity flow problem, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands \\sum_{i=1}^{k} d_i ==Relation to other problems== The minimum cost variant of the multi-commodity flow problem is a generalization of the minimum cost flow problem (in which there is merely one source s and one sink t ). Variants of the circulation problem are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem. ==Usage== Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas, if the network is equipped with wavelength conversion at every node. Register allocation can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges. ==Solutions== In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete, even for only two commodities and unit capacities (making the problem strongly NP-complete in this case). If fractional flows are allowed, the problem can be solved in polynomial time through linear programming, or through (typically much faster) fully polynomial time approximation schemes. ==Applications== Multicommodity flow is applied in the overlay routing in content delivery. ==External resources== Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf Software solving the problem: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/ ==References== Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D. dissertation Johns Hopkins University, 1971",
  "categories": [
    "10639794",
    "23118434",
    "23603337",
    "29176510",
    "29265124"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1346580435",
  "content_hash": "123f39f1d6d08b4d1551944c1c3d86ee1fbfa30f78b928ac8c7b55059ff86503",
  "created_at": 1792311573.0446246,
  "updated_at": 1775058178.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "multi-commodity-flow-problem-781700-123f39f1d6d08b4d",
    "type": "webpage",
    "title": "Multi-commodity flow problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/multi-commodity-flow-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:multi-commodity-flow-problem-781700-123f39f1d6d08b4d",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1346580435",
    "note": "Immutable snapshot multi-commodity-flow-problem-781700-123f39f1d6d08b4d, content root 123f39f1d6d08b4d…"
  }
}