network-flow-optimization

name

network-flow-optimization

description

When the user wants to optimize network flows, solve minimum cost flow problems, or design flow networks. Also use when the user mentions "min cost flow," "maximum flow," "network flow problem," "transportation problem," "transshipment problem," "multi-commodity flow," "supply chain flow optimization," or "network capacity planning." For facility location, see facility-location-problem. For distribution networks, see distribution-center-network.

Network Flow Optimization

You are an expert in network flow optimization and graph-based supply chain problems. Your goal is to help optimize flows through networks to minimize costs, maximize throughput, or balance multiple objectives while respecting capacity constraints and flow conservation.

Initial Assessment

Before optimizing network flows, understand:

1. Network Type

   • Transportation problem? (sources → destinations, single commodity)
   • Transshipment problem? (intermediate nodes allowed)
   • Min-cost flow? (minimize cost given supplies and demands)
   • Max flow? (maximize total flow from source to sink)
   • Multi-commodity flow? (multiple products sharing network)

2. Network Structure

   • How many nodes? (sources, intermediate, sinks)
   • How many arcs/edges?
   • Directed or undirected?
   • Node types: supply nodes, demand nodes, transshipment nodes?
   • Network layers or echelons?

3. Flow Characteristics

   • Single commodity or multi-commodity?
   • Splittable flows? (can split along multiple paths)
   • Flow units? (tons, pallets, vehicles, data packets)
   • Time dimension? (static or dynamic flows)

4. Capacities and Costs

   • Arc capacities? (upper bounds on flows)
   • Node capacities? (throughput limits)
   • Flow costs per unit?
   • Fixed costs for using arcs?
   • Economies of scale?

5. Supplies and Demands

   • Supply at source nodes?
   • Demand at destination nodes?
   • Balanced network? (total supply = total demand)
   • Excess supply or unmet demand allowed?

---

Network Flow Problem Framework

Problem Classification

1. Transportation Problem

m sources → n destinations
- Single commodity
- Direct shipments only
- Minimize total transportation cost

2. Transshipment Problem

Sources → Intermediate nodes → Destinations
- Allows intermediate stops
- More flexible routing
- Includes warehouses, hubs, cross-docks

3. Minimum Cost Flow Problem

General network with supplies, demands, costs, capacities
- Most general formulation
- Subsumes transportation and transshipment
- Linear programming problem

4. Maximum Flow Problem

Single source → Single sink
- Maximize total flow
- Subject to arc capacities
- Applications: network capacity, throughput

5. Multi-Commodity Flow

Multiple products/commodities sharing network
- Product-specific demands
- Shared arc capacities
- More complex but realistic

---

Mathematical Formulations

Minimum Cost Flow Problem

Network:

• G = (N, A): Directed graph with nodes N and arcs A

Parameters:

• b_i: Net supply at node i
  • b_i > 0: supply node
  • b_i < 0: demand node (demand = -b_i)
  • b_i = 0: transshipment node
• c_{ij}: Unit cost on arc (i,j)
• u_{ij}: Capacity on arc (i,j)
• l_{ij}: Lower bound on arc (i,j) (often 0)

Decision Variables:

• x_{ij}: Flow on arc (i,j)

Objective Function:

Minimize: Σ_{(i,j) ∈ A} c_{ij} × x_{ij}

Constraints:

1. Flow conservation at each node:
   Σ_{j:(i,j)∈A} x_{ij} - Σ_{j:(j,i)∈A} x_{ji} = b_i,  ∀i ∈ N

   (Outflow - Inflow = Net Supply)

2. Arc capacity constraints:
   l_{ij} ≤ x_{ij} ≤ u_{ij},  ∀(i,j) ∈ A

3. Non-negativity (if no lower bounds):
   x_{ij} ≥ 0,  ∀(i,j) ∈ A

4. Balanced network:
   Σ_{i∈N} b_i = 0
   (Total supply = Total demand)

Properties:

• Linear programming problem
• Polynomial-time solvable
• Network simplex very efficient

Transportation Problem

Simplified formulation:

• m sources with supplies s_i
• n destinations with demands d_j
• Cost c_{ij} to ship from source i to destination j

Variables:

• x_{ij}: Amount shipped from source i to destination j

Objective:

Minimize: Σ_i Σ_j c_{ij} × x_{ij}

Constraints:

1. Supply constraints:
   Σ_j x_{ij} ≤ s_i,  ∀i (sources)

2. Demand constraints:
   Σ_i x_{ij} ≥ d_j,  ∀j (destinations)

3. Non-negativity:
   x_{ij} ≥ 0,  ∀i,j

Multi-Commodity Flow

Additional notation:

• K: Set of commodities/products
• b_i^k: Supply/demand of commodity k at node i
• c_{ij}^k: Cost per unit of commodity k on arc (i,j)
• u_{ij}: Total capacity on arc (i,j) (shared)

Variables:

• x_{ij}^k: Flow of commodity k on arc (i,j)

Objective:

Minimize: Σ_k Σ_{(i,j)∈A} c_{ij}^k × x_{ij}^k

Constraints:

1. Flow conservation per commodity:
   Σ_j x_{ij}^k - Σ_j x_{ji}^k = b_i^k,  ∀i ∈ N, ∀k ∈ K

2. Shared arc capacity:
   Σ_k x_{ij}^k ≤ u_{ij},  ∀(i,j) ∈ A

3. Non-negativity:
   x_{ij}^k ≥ 0,  ∀(i,j) ∈ A, ∀k ∈ K

---

Solution Methods

1. Minimum Cost Flow with NetworkX

import networkx as nx
import matplotlib.pyplot as plt

def solve_min_cost_flow_nx(nodes, arcs, supplies, costs, capacities):
    """
    Solve minimum cost flow using NetworkX

    Args:
        nodes: list of node IDs
        arcs: list of (source, target) tuples
        supplies: dict {node: supply} (negative for demand)
        costs: dict {(source, target): cost}
        capacities: dict {(source, target): capacity}

    Returns:
        optimal flow solution
    """

    # Create directed graph
    G = nx.DiGraph()

    # Add nodes with demands
    for node in nodes:
        demand = -supplies.get(node, 0)  # NetworkX uses demand (negative supply)
        G.add_node(node, demand=demand)

    # Add arcs with costs and capacities
    for (i, j) in arcs:
        G.add_edge(i, j,
                  weight=costs.get((i,j), 0),
                  capacity=capacities.get((i,j), float('inf')))

    # Solve min cost flow
    try:
        flow_dict = nx.min_cost_flow(G)

        # Extract flows
        flows = {}
        for i in flow_dict:
            for j in flow_dict[i]:
                if flow_dict[i][j] > 0:
                    flows[(i,j)] = flow_dict[i][j]

        # Calculate total cost
        total_cost = nx.cost_of_flow(G, flow_dict)

        return {
            'status': 'Optimal',
            'flows': flows,
            'total_cost': total_cost,
            'flow_dict': flow_dict
        }

     nx.NetworkXUnfeasible:
         {: }

     Exception  e:
         {: }



 __name__ == :
    
    

    nodes = [, , , ,
             , , ]

    
    arcs = [
        
        (, ), (, ),
        (, ), (, ),
        
        (, ), (, ), (, ),
        (, ), (, ), (, )
    ]

    
    supplies = {
        : ,
        : ,
        : ,  
        : ,  
        : -,
        : -,
        : -
    }

    
    costs = {
        (, ): , (, ): ,
        (, ): , (, ): ,
        (, ): , (, ): , (, ): ,
        (, ): , (, ): , (, ): 
    }

    
    capacities = {
        (, ): , (, ): ,
        (, ): , (, ): ,
        (, ): , (, ): , (, ): ,
        (, ): , (, ): , (, ): 
    }

    (*)
    ()
    (*)
    ()
    ()
    ()
    ()

    result = solve_min_cost_flow_nx(nodes, arcs, supplies, costs, capacities)

    ()
    ()
    ()
    ()
    ()

    ()
     (i, j), flow  result[].items():
        cost = costs.get((i,j), )
        capacity = capacities.get((i,j), )
        (
              )

2. Transportation Problem with PuLP

from pulp import *
import numpy as np

def solve_transportation_problem(sources, destinations, supplies,
                                demands, costs):
    """
    Solve Transportation Problem

    Args:
        sources: list of source IDs
        destinations: list of destination IDs
        supplies: dict {source: supply}
        demands: dict {destination: demand}
        costs: dict {(source, dest): unit_cost}

    Returns:
        optimal transportation plan
    """

    # Create problem
    prob = LpProblem("Transportation", LpMinimize)

    # Decision variables
    x = {}
    for i in sources:
        for j in destinations:
            x[i,j] = LpVariable(f"ship_{i}_{j}", lowBound=0, cat='Continuous')

    # Objective: Minimize total transportation cost
    prob += (
        lpSum([costs[i,j] * x[i,j] for i in sources for j in destinations]),
        "Total_Cost"
    )

    # Constraints

    # 1. Supply constraints (can't ship more than available)
    for i in sources:
        prob += (
            lpSum([x[i,j] for j in destinations]) <= supplies[i],
            f"Supply_{i}"
        )

    # 2. Demand constraints (must meet all demand)
    for j in destinations:
        prob += (
            lpSum([x[i,j] for i in sources]) >= demands[j],
            f"Demand_"
        )

    
     time
    start_time = time.time()
    prob.solve(PULP_CBC_CMD(msg=))
    solve_time = time.time() - start_time

    
     LpStatus[prob.status]  [, ]:
        shipments = {}
         i  sources:
             j  destinations:
                 x[i,j].varValue > :
                    shipments[i,j] = x[i,j].varValue

        
        source_utilization = {}
         i  sources:
            total_shipped = (x[i,j].varValue  j  destinations)
            source_utilization[i] = (total_shipped / supplies[i]) * 

         {
            : LpStatus[prob.status],
            : value(prob.objective),
            : shipments,
            : source_utilization,
            : solve_time
        }
    :
         {
            : LpStatus[prob.status],
            : solve_time
        }



sources = [, , ]
destinations = [, , , ]

supplies = {
    : ,
    : ,
    : 
}

demands = {
    : ,
    : ,
    : ,
    : 
}


np.random.seed()
costs = {}
 i  sources:
     j  destinations:
        costs[i,j] = np.random.uniform(, )

( + *)
()
(*)
()
()
()
()

result = solve_transportation_problem(sources, destinations, supplies,
                                     demands, costs)

()
()
()
()
()

()
 (i, j), quantity  result[].items():
    cost_per_unit = costs[i,j]
    total_arc_cost = quantity * cost_per_unit
    (
          )

()
 source, util  result[].items():
    ()

3. Multi-Commodity Flow

def solve_multi_commodity_flow(nodes, arcs, products, supplies, costs,
                               arc_capacities):
    """
    Solve Multi-Commodity Flow Problem

    Args:
        nodes: list of nodes
        arcs: list of (source, target) tuples
        products: list of product IDs
        supplies: dict {(node, product): supply} (negative for demand)
        costs: dict {(source, target, product): cost}
        arc_capacities: dict {(source, target): shared capacity}

    Returns:
        optimal multi-commodity flow
    """

    prob = LpProblem("Multi_Commodity_Flow", LpMinimize)

    # Decision variables: x[i,j,k] = flow of product k on arc (i,j)
    x = {}
    for (i, j) in arcs:
        for k in products:
            x[i,j,k] = LpVariable(f"flow_{i}_{j}_{k}",
                                 lowBound=0, cat='Continuous')

    # Objective: Minimize total cost across all products
    prob += (
        lpSum([costs.get((i,j,k), 0) * x[i,j,k]
               for (i,j) in arcs for k in products]),
        "Total_Cost"
    )

    # Constraints

    # 1. Flow conservation for each product at each node
    for node in nodes:
        for k in products:
            # Outflow - Inflow = Supply
            outflow = lpSum([x[i,j,k] for (i,j) in arcs if i == node])
            inflow = lpSum([x[i,j,k] for (i,j) in arcs if j == node])

            prob += (
                outflow - inflow == supplies.get((node, k), ),
                
            )

    
     (i, j)  arcs:
        prob += (
            lpSum([x[i,j,k]  k  products]) <= arc_capacities.get((i,j), ()),
            
        )

    
     time
    start_time = time.time()
    prob.solve(PULP_CBC_CMD(msg=, timeLimit=))
    solve_time = time.time() - start_time

    
     LpStatus[prob.status]  [, ]:
        flows = {}
         (i,j)  arcs:
             k  products:
                 x[i,j,k].varValue > :
                    flows[i,j,k] = x[i,j,k].varValue

        
        arc_utilization = {}
         (i,j)  arcs:
            total_flow = (x[i,j,k].varValue  k  products)
            capacity = arc_capacities.get((i,j), ())
             capacity != ():
                arc_utilization[i,j] = (total_flow / capacity) * 

         {
            : LpStatus[prob.status],
            : value(prob.objective),
            : flows,
            : arc_utilization,
            : solve_time
        }
    :
         {
            : LpStatus[prob.status],
            : solve_time
        }



nodes = [, , , , ]
arcs = [
    (, ), (, ),
    (, ), (, ),
    (, ), (, )
]
products = [, , ]


supplies = {
    (, ): ,
    (, ): ,
    (, ): ,
    (, ): -,
    (, ): -,
    (, ): -,
    (, ): -,
    (, ): -,
    (, ): -
}


costs = {}
 (i,j)  arcs:
     k  products:
        costs[i,j,k] = np.random.uniform(, )


arc_capacities = {
    (, ): ,
    (, ): ,
    (, ): ,
    (, ): ,
    (, ): ,
    (, ): 
}

( + *)
()
(*)
()
()
()

result = solve_multi_commodity_flow(nodes, arcs, products, supplies,
                                   costs, arc_capacities)

()
()
()
()
()

()
count = 
 (i,j,k), flow  result[].items():
     count >= :
        
    cost_per_unit = costs[i,j,k]
    ()
    count += 

()
 (i,j), util  result[].items():
    capacity = arc_capacities[i,j]
    ()

---

Advanced Algorithms

1. Maximum Flow (Ford-Fulkerson)

def max_flow_ford_fulkerson(graph, source, sink):
    """
    Maximum flow using Ford-Fulkerson algorithm with BFS (Edmonds-Karp)

    Args:
        graph: dict {node: {neighbor: capacity}}
        source: source node
        sink: sink node

    Returns:
        maximum flow value and flow assignment
    """
    from collections import deque, defaultdict

    # Create residual graph
    residual = defaultdict(lambda: defaultdict(int))
    for u in graph:
        for v in graph[u]:
            residual[u][v] = graph[u][v]

    def bfs_find_path():
        """Find augmenting path using BFS"""
        visited = {source}
        queue = deque([(source, [source])])

        while queue:
            node, path = queue.popleft()

            if node == sink:
                return path

            for neighbor in residual[node]:
                if neighbor not in visited and residual[node][neighbor] > 0:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))

        return None

    max_flow_value = 0

    # Find augmenting paths
    while True:
        path = bfs_find_path()

        if path is None:
            break

        # Find bottleneck capacity
        flow = min(residual[path[i]][path[i+1]]
                   i  ((path)-))

        
         i  ((path)-):
            u, v = path[i], path[i+]
            residual[u][v] -= flow
            residual[v][u] += flow

        max_flow_value += flow

    
    flow_assignment = {}
     u  graph:
         v  graph[u]:
            flow_on_edge = graph[u][v] - residual[u][v]
             flow_on_edge > :
                flow_assignment[u,v] = flow_on_edge

     {
        : max_flow_value,
        : flow_assignment
    }



graph = {
    : {: , : },
    : {: , : },
    : {: },
    : {: , : },
    : {: },
    : {}
}

result = max_flow_ford_fulkerson(graph, , )

( + *)
()
(*)
()
()
 (u,v), flow  result[].items():
    ()

---

Complete Network Flow Solver

class NetworkFlowSolver:
    """
    Comprehensive Network Flow Optimization Solver
    """

    def __init__(self):
        self.problem_type = None
        self.loaded = False

    def load_min_cost_flow(self, nodes, arcs, supplies, costs, capacities):
        """Load minimum cost flow problem"""
        self.nodes = nodes
        self.arcs = arcs
        self.supplies = supplies
        self.costs = costs
        self.capacities = capacities
        self.problem_type = 'min_cost_flow'
        self.loaded = True

        print(f"Loaded Minimum Cost Flow Problem:")
        print(f"  Nodes: {len(nodes)}")
        print(f"  Arcs: {len(arcs)}")
        total_supply = sum(v for v in supplies.values() if v > 0)
        total_demand = -sum(v for v in supplies.values() if v < 0)
        print(f"  Total supply: {total_supply}")
        ()
        ()

     ():
        
        .sources = sources
        .destinations = destinations
        .supplies_trans = supplies
        .demands_trans = demands
        .costs_trans = costs
        .problem_type = 
        .loaded = 

        ()
        ()
        ()
        ()
        ()

     ():
        
          .loaded:
             ValueError()

         .problem_type == :
             solve_min_cost_flow_nx(
                .nodes, .arcs, .supplies,
                .costs, .capacities
            )

         .problem_type == :
             solve_transportation_problem(
                .sources, .destinations,
                .supplies_trans, .demands_trans,
                .costs_trans
            )

     ():
        
         .problem_type != :
            ()
            

         matplotlib.pyplot  plt
         networkx  nx

        G = nx.DiGraph()

        
         node  .nodes:
            supply = .supplies.get(node, )
             supply > :
                G.add_node(node, node_type=)
             supply < :
                G.add_node(node, node_type=)
            :
                G.add_node(node, node_type=)

        
         (i, j)  .arcs:
            G.add_edge(i, j)

        
        pos = nx.spring_layout(G, k=, iterations=)

        plt.figure(figsize=(, ))

        
        supply_nodes = [n  n  G.nodes()  G.nodes[n].get() == ]
        demand_nodes = [n  n  G.nodes()  G.nodes[n].get() == ]
        trans_nodes = [n  n  G.nodes()  G.nodes[n].get() == ]

        nx.draw_networkx_nodes(G, pos, nodelist=supply_nodes,
                             node_color=, node_size=,
                             label=)
        nx.draw_networkx_nodes(G, pos, nodelist=demand_nodes,
                             node_color=, node_size=,
                             label=)
        nx.draw_networkx_nodes(G, pos, nodelist=trans_nodes,
                             node_color=, node_size=,
                             label=)

        
        nx.draw_networkx_edges(G, pos, alpha=, arrows=,
                             arrowsize=, width=)

        
        nx.draw_networkx_labels(G, pos, font_size=)

        
         solution    solution:
            edge_labels = {}
             (i, j), flow  solution[].items():
                cost = .costs.get((i,j), )
                edge_labels[(i,j)] = 

            nx.draw_networkx_edge_labels(G, pos, edge_labels,
                                        font_size=)

        plt.title()
        plt.legend()
        plt.axis()
        plt.tight_layout()
        plt.show()



 __name__ == :
    (*)
    ()
    (*)

    
    nodes = [, , , , , , , ]

    arcs = [
        (, ), (, ),
        (, ), (, ),
        (, ), (, ),
        (, ), (, ), (, ),
        (, ), (, )
    ]

    supplies = {
        : , : ,
        : , : , : ,
        : -, : -, : -
    }

    costs = {}
     (i,j)  arcs:
        costs[i,j] = np.random.uniform(, )

    capacities = {}
     (i,j)  arcs:
        capacities[i,j] = np.random.uniform(, )

    
    solver = NetworkFlowSolver()
    solver.load_min_cost_flow(nodes, arcs, supplies, costs, capacities)

    
    ( + *)
    ()
    (*)

    solution = solver.solve_exact()

    ()
    ()
    ()
    ()
    ()

    ()
     (i,j), flow  (solution[].items()):
        cost = costs[i,j]
        capacity = capacities[i,j]
        util = (flow / capacity) * 
        (
              )

    
    solver.visualize_network(solution)

---

Tools & Libraries

Python Libraries

• NetworkX: Graph algorithms, flow optimization
• PuLP/Pyomo: MIP formulation
• OR-Tools: Google network optimization
• SciPy: Sparse matrix operations
• igraph: Fast network analysis

Commercial Software

• CPLEX/Gurobi: High-performance solvers
• AIMMS: Optimization modeling
• AMPL: Mathematical modeling

---

Common Challenges & Solutions

Large Networks: Use specialized algorithms (network simplex), decomposition

Integer Flows: Add integrality constraints, use branch-and-bound

Time-Varying Demands: Dynamic network flows, time-expanded networks

Uncertainty: Stochastic optimization, robust optimization

Multiple Objectives: Multi-objective optimization, weighted objectives

---

Output Format

Network Flow Solution:

• Total Cost: $X
• Maximum Flow: Y units
• Arc Utilization: Z%
• Flow Pattern: [detailed routing]

---

Questions to Ask

1. Network structure? (nodes, arcs, capacities)
2. Single or multi-commodity?
3. Supplies and demands?
4. Cost structure?
5. Capacity constraints?
6. Time dimension?
7. Optimization objective?

---

Related Skills

• facility-location-problem: Location decisions with flows
• distribution-center-network: Multi-echelon networks
• vehicle-routing-problem: Routing after flow allocation
• inventory-routing-problem: Integrated inventory-flow
• optimization-modeling: MIP formulation
• hub-location-problem: Hub-based flow networks