Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Min Cost Flow Slotting › Visualizing Minimum Cost flow

Michael BrenndoerferSeptember 1, 20257 min read

Machine Learning from ScratchAll chapters

Part 9 of 9Optimization

Chapter 63Min Cost Flow Slotting › Visualizing Minimum Cost flow

Reading section 3 of 8 · Visualizing Minimum Cost flow · 7 minSection 3 of 8 · 7 min

Section 3 of 8 · 7 min read

Min Cost Flow Slotting › Visualizing Minimum Cost flowOne section · Sections in this chapter3 / 8 ↓

Sections in this chapter8

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's create visualizations to understand how the Minimum Cost flow problem works in practice. We'll start by setting up the necessary libraries and creating a simple example.

Out[4]:

Visualization

Four-node directed network from factory to market through warehouse and distribution, with every edge labeled by cost and capacity. — Minimum cost flow network connecting a factory with supply 10 to a market with demand 10 through warehouse and distribution transshipment nodes. Every directed edge is labeled with its unit cost and capacity, showing the feasible routes whose combined cost the optimization minimizes.

Now let's solve this network using OR-Tools and visualize the optimal flow:

In[5]:

Code

from ortools.graph.python import min_cost_flow


def solve_mcf_ortools(G):
    """solve the MCF problem using OR-Tools"""
    # Create the solver
    solver = min_cost_flow.SimpleMinCostFlow()

    # Extract network data
    start_nodes = []
    end_nodes = []
    capacities = []
    unit_costs = []
    supplies = []

    # Add edges
    for u, v in G.edges():
        start_nodes.append(u)
        end_nodes.append(v)
        capacities.append(G[u][v]["capacity"])
        unit_costs.append(G[u][v]["cost"])

    # Add supplies
    for node in G.nodes():
        supplies.append(G.nodes[node]["supply"])

    # Add arcs to the solver
    for i in range(len(start_nodes)):
        solver.add_arc_with_capacity_and_unit_cost(
            start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]
        )

    # Add node supplies
    for i in range(len(supplies)):
        solver.set_node_supply(i, supplies[i])

    # solve
    status = solver.solve()

    if status == solver.OPTIMAL:
        print(f"Minimum cost: {solver.optimal_cost()}")
        print("\nOptimal flow:")
        print("Arc    flow / capacity  Cost")

        flows = {}
        for i in range(solver.num_arcs()):
            tail = solver.tail(i)
            head = solver.head(i)
            flow = solver.flow(i)
            capacity = solver.capacity(i)
            cost = solver.flow(i) * solver.unit_cost(i)

            flows[(tail, head)] = flow
            print(f"{tail} -> {head}   {flow}  / {capacity}       {cost}")

        return flows, solver.optimal_cost()
    else:
        print("No optimal solution found")
        return None, None


# solve the problem
flows, total_cost = solve_mcf_ortools(G)

Out[5]:

Console

Minimum cost: 60

Optimal flow:
Arc    flow / capacity  Cost
0 -> 1   10  / 15       40
0 -> 2   0  / 8       0
1 -> 3   10  / 10       20
1 -> 2   0  / 5       0
2 -> 3   0  / 12       0

Out[6]:

Visualization

Four-node network with the optimal Factory-to-Warehouse-to-Market route highlighted, both arcs labeled with flow 10 and unit cost, and total cost 60 in the title. — Optimal flow solution found by OR-Tools. The highlighted route sends 10 units from Factory to Warehouse at cost 4 per unit, then 10 units from Warehouse to Market at cost 2 per unit, for a minimum total cost of 60. Nodes retain their supply, demand, and transshipment roles.