MIN_COST_FLOW_COST

Minimum cost flow problems involve finding the most cost-effective way to transport a certain amount of “commodity” (flow) through a network. Each edge has a capacity and a cost per unit of flow, and nodes can have demands (positives for sinks, negatives for sources).

This is highly useful for supply chain optimization, transportation logistics, and resource allocation where you need to meet requirements while minimizing expenses.

This function returns the total minimum cost to satisfy the given demands.

Excel Usage

=MIN_COST_FLOW_COST(edges, demands)
  • edges (list[list], required): 2D array of edges [source, target, cost, capacity].
  • demands (list[list], required): 2D array of node demands [node, demand]. Negative for supply, positive for demand.

Returns (float): Minimum cost of flow.

Example 1: Simple supply-demand network

Inputs:

edges demands
A B 3 4 A -5
A C 6 10 D 5
B D 1 9
C D 2 5

Excel formula:

=MIN_COST_FLOW_COST({"A","B",3,4;"A","C",6,10;"B","D",1,9;"C","D",2,5}, {"A",-5;"D",5})

Expected output:

24

Example 2: Multiple sources and sinks

Inputs:

edges demands
S1 A 1 S1 -10
S2 A 2 S2 -10
A T1 3 T1 10
A T2 4 T2 10

Excel formula:

=MIN_COST_FLOW_COST({"S1","A",1;"S2","A",2;"A","T1",3;"A","T2",4}, {"S1",-10;"S2",-10;"T1",10;"T2",10})

Expected output:

100

Example 3: Simple bridge with costs

Inputs:

edges demands
A B 1 10 A -5
B C 1 10 C 5

Excel formula:

=MIN_COST_FLOW_COST({"A","B",1,10;"B","C",1,10}, {"A",-5;"C",5})

Expected output:

10

Example 4: High cost short path vs low cost long path

Inputs:

edges demands
A D 10 10 A -1
A B 1 10 D 1
B C 1 10
C D 1 10

Excel formula:

=MIN_COST_FLOW_COST({"A","D",10,10;"A","B",1,10;"B","C",1,10;"C","D",1,10}, {"A",-1;"D",1})

Expected output:

3

Python Code

import networkx as nx

def min_cost_flow_cost(edges, demands):
    """
    Find the minimum cost to satisfy all demands in a network.

    See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.min_cost_flow_cost.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        edges (list[list]): 2D array of edges [source, target, cost, capacity].
        demands (list[list]): 2D array of node demands [node, demand]. Negative for supply, positive for demand.

    Returns:
        float: Minimum cost of flow.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        edges = to2d(edges)
        demands = to2d(demands)

        if not isinstance(edges, list) or not edges:
            return "Error: edges must be a non-empty 2D list"

        if not isinstance(demands, list) or not demands:
            return "Error: demands must be a non-empty 2D list"

        G = nx.DiGraph()

        # Process demands
        for row in demands:
            if not isinstance(row, list) or len(row) < 2:
                continue

            node, demand = str(row[0]), float(row[1])
            G.add_node(node, demand=demand)

        # Process edges
        for row in edges:
            if not isinstance(row, list) or len(row) < 3:
                continue

            u, v = str(row[0]), str(row[1])
            # [u, v, cost, capacity]
            cost = float(row[2])
            cap = float(row[3]) if len(row) >= 4 else float('inf')
            G.add_edge(u, v, weight=cost, capacity=cap)

        if G.number_of_nodes() == 0:
            return "Error: No valid demand rows found in input"

        if G.number_of_edges() == 0:
            return "Error: No valid edge rows found in input"

        try:
            total_cost = nx.min_cost_flow_cost(G)
            return float(total_cost)
        except nx.NetworkXUnfeasible:
            return "Error: No flow exists that satisfies all demands (sum of demands must be 0 and capacities must suffice)"
        except nx.NetworkXUnbounded:
            return "Error: Flow is unbounded below (negative cost cycle with infinite capacity)"

    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

2D array of edges [source, target, cost, capacity].
2D array of node demands [node, demand]. Negative for supply, positive for demand.