{
  "id": "enwiki-001370483180",
  "slug": "minimum-cost-flow-problem",
  "title": "Minimum-cost flow problem",
  "qid": "",
  "lead": "The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.",
  "body": "The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm. A flow network is a directed graph G=(V,E) with a source vertex s \\in V and a sink vertex t \\in V , where each edge (u,v) \\in E has capacity c(u,v) > 0 , flow f(u,v) and cost a(u,v) , with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge (u,v) is f(u,v)\\cdot a(u,v) . The problem requires an amount of flow d to be sent from source s to sink t . The definition of the problem is to minimize the total cost of the flow over all edges: \\sum_{(u,v) \\in E} a(u,v) \\cdot f(u,v) with the constraints A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. The minimum cost circulation problem has no source and sink; instead it has costs and lower and upper bounds on each edge, and seeks flow amounts within the given bounds that balance the flow at each vertex and minimize the sum over edges of cost times flow. Any minimum-cost flow instance can be converted into a minimum cost circulation instance by setting the lower bound on all edges to zero, and then making an extra edge from the sink t to the source s , with capacity c(t,s)=d and lower bound l(t,s)=d , forcing the total flow from s to t to also be d . The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn): Shortest path problem (single-source). Require that a feasible solution to the minimum cost flow problem sends one unit of flow from a designated source s to a designated sink t . Give all edges infinite capacity. Maximum flow problem. Choose a large demand d (large enough to exceed the maximum flow; for instance, the sum of capacities out of the source vertex) Set the costs of all edges in the maximum flow instance to zero, and introduce a new edge from source to sink with unit cost and capacity d . Assignment problem. Suppose that each partite set in the bipartition has n vertices, and denote the bipartition by (X,Y) . Give each x \\in X supply 1/n and give each y \\in Y demand 1/n . Each edge is to have unit capacity. ===Cycle canceling algorithms=== These algorithms are iterative and like the Ford–Fulkerson algorithm they define a residual graph. If there is flow f(u,v) on arc e=(u,v) , then its residual capacity is defined to be c(e)-f(e) and its residual cost is a(e) . The reverse arc (which has negative flow value) has a negative cost -a(e) . The algorithms then start with an arbitrary feasible flow and iteratively improve the cost of the solution by pushing flow around negative-cost cycles. In the Minimum mean cycle canceling, the algorithm selects a cycle that has minimum mean cost (the ratio of the total cycle cost to the number of arcs). Such a cycle can be found in polynomial time (by binary search using the Bellman-Ford algorithm) and the total number of iterations has been proven to be polynomial . ===Almost-linear time algorithm=== A deterministic almost-linear time algorithm is known to solve the minimum-cost flow problem on directed graphs. That is, on a graph with m edges and polynomially bounded demands, costs, and capacities, the algorithm runs in time m^{1+o(1)} .",
  "categories": [
    "20477143",
    "23603337",
    "26220375",
    "29176510"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1370483180",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1787301228.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001370483180",
    "type": "webpage",
    "title": "Minimum-cost 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/minimum-cost-flow-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001370483180",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1370483180",
    "note": "Immutable snapshot enwiki-001370483180"
  }
}