Network Flow Optimization

Overview

This project was built as part of CSCE 5210 at the University of North Texas. The challenge was to implement a heuristic approach to the maximum flow problem — assigning flow through a directed graph while respecting edge capacities and flow conservation at internal nodes — and then benchmark it against the exact Edmonds-Karp algorithm.

The full implementation is available in the Google Colab notebook.

The approach uses a simulated annealing-style search that randomly selects paths, assigns flow values, enforces constraints through iterative rebalancing, and accepts or rejects solutions based on a temperature-dependent probability function.

Architecture

Graph Construction

Each graph is a directed NetworkX graph where edges have capacity and flow attributes. The new_G function generates random graphs and validates that a path exists from source to sink before assigning random capacities:

def new_G(n, p, source, sink):
  G = new_directed_G(n=n, p=p)
  while G_is_invalid(G=G, source=source, sink=sink):
    G = new_directed_G(n=n, p=p)

  for edge in list(G.edges()):
    G.edges[edge]['flow'] = 0
    G.edges[edge]['capacity'] = random.randint(1, 10)

  return G

The validation check ensures weak connectivity and that a path exists from source to sink, retrying graph generation until both conditions are met.

Boltzmann Acceptance Criterion

The core of the simulated annealing approach is the acceptance function. Better solutions (higher flow) are always accepted. Worse solutions are accepted with a probability based on the Boltzmann distribution, allowing the search to escape local optima:

def should_use_path(c_flow, n_flow, t):
  if n_flow > c_flow or c_flow == 0:
    return True

  return random.random() <= math.exp((n_flow - c_flow) / t)

At high temperatures, the algorithm is more exploratory and accepts worse solutions more often. As the temperature cools, it becomes increasingly greedy, converging toward the best solution found.

Flow Conservation Enforcement

After modifying flow along a path, internal nodes may violate conservation (total in-flow must equal total out-flow). The validate_node function detects and fixes imbalances by decrementing excess flow on edges, and run_constraints_check propagates these fixes through the graph using a queue:

def validate_node(G, node):
  changed_nodes = []
  in_edges = list(G.in_edges(node))
  out_edges = list(G.out_edges(node))
  total_in = get_edges_flow_sum(G=G, edges=in_edges)
  total_out = get_edges_flow_sum(G=G, edges=out_edges)

  if total_in == total_out:
    return changed_nodes

  if total_out > total_in:
    total_out = balance_capacity(
      G=G, edges=out_edges, adjust_val=total_out,
      comp_val=total_in, changed_nodes=changed_nodes,
      get_node=lambda edge: edge[1]
    )

  if total_in > total_out:
    total_in = balance_capacity(
      G=G, edges=in_edges, adjust_val=total_in,
      comp_val=total_out, changed_nodes=changed_nodes,
      get_node=lambda edge: edge[0]
    )

  return changed_nodes

When a node is rebalanced, its neighbors may become unbalanced in turn. The constraint check queues affected neighbors and iterates until the entire graph satisfies conservation.

Driver Loop with Cooling Schedule

The driver function ties everything together. Each iteration picks a random source-to-sink path, assigns a random flow value (bounded by the path's minimum edge capacity), enforces constraints, and decides whether to keep the result:

while temp > 0:
  next_G = copy.deepcopy(G)
  path = random.choice(paths)
  path_flow_val = get_next_value_for_path(G=next_G, path=path)
  for edge in edges_from_path(path):
    next_G.edges[edge]['flow'] = path_flow_val

  run_constraints_check(
    G=next_G,
    queue=get_internal_nodes(path=path, source=source, sink=sink)
  )

  next_flow = get_sink_flow_total(G=next_G, sink=sink)
  if should_use_path(c_flow=c_flow, n_flow=next_flow, t=temp):
    G = next_G
    c_flow = next_flow
    if c_flow > best_flow:
      best_graph = copy.deepcopy(G)
      best_flow = int(c_flow)

  iteration -= 1
  if iteration == 0:
    temp = temp * (1 - a)
    iteration = 20

The temperature decreases by a factor of (1-a) every 20 iterations, gradually shifting the search from exploration to exploitation.

Edmonds-Karp Benchmarking

After the heuristic completes, the exact Edmonds-Karp maximum flow is computed on the same graph to evaluate solution quality:

def run_edmunds_karp(G, source, sink):
  return nx.maximum_flow_value(
    G, source, sink,
    capacity='capacity',
    flow_func=edmonds_karp
  )

This provides a ground truth to measure how close the heuristic gets to optimal.

Scenarios

The project tests across multiple configurations:

• R1: A fixed 6-node graph with labeled nodes (S, U, V, W, E, Z) and known capacities, useful for verifying correctness
• R2: A random 30-node graph with connectivity 0.1
• R3: 30 independent runs on random 30-node graphs, comparing average heuristic flow vs Edmonds-Karp flow at temperature 100 (R3a) and temperature 1000 (R3b) to study how initial temperature affects solution quality