12.25 Common Flow Modeling Patterns

Problem

Many optimization problems appear completely different on the surface.

Consider these examples:

Assign nurses to hospital shifts.
Match students to courses.
Route packages through warehouses.
Allocate cloud resources to applications.
Schedule manufacturing jobs.
Select profitable projects.
Segment an image.
Verify network reliability.

The problem statements use different terminology and come from different domains. Yet experienced algorithm designers often solve all of them with network flow.

The challenge is learning to recognize the patterns.

Solution

Instead of memorizing individual reductions, learn the common modeling templates.

Most flow applications are variations of a small number of network structures:

Supply → Demand
Bipartite Assignment
Capacity-Constrained Routing
Selection with Dependencies
Time-Expanded Networks
Resource Allocation
Disjoint Path Problems
Feasibility with Lower Bounds
Cost Optimization
Segmentation and Partitioning

When a new problem appears, identify which template it resembles.

Pattern 1: Supply to Demand

The simplest flow model moves resources from producers to consumers.

Structure:

source
  ↓
suppliers
  ↓
consumers
  ↓
sink

Capacities:

source -> supplier

represent available supply.

Capacities:

consumer -> sink

represent demand.

Flow value represents the amount delivered.

Example

Factories:

Factory	Supply
F1	10
F2	15

Stores:

Store	Demand
S1	8
S2	12
S3	5

The maximum flow determines whether all demand can be satisfied.

Pattern 2: Bipartite Assignment

Assignments are everywhere.

Structure:

source
  ↓
left side
  ↓
right side
  ↓
sink

Examples:

Left	Right
Workers	Jobs
Students	Courses
Doctors	Shifts
Drivers	Routes
Servers	Tasks

Capacity:

on assignment edges usually means one-to-one matching.

Example

Workers -> Shifts

Edge exists only when:

worker is available

A maximum matching becomes a feasible assignment.

Pattern 3: Capacity-Constrained Routing

Some problems involve moving flow through a network.

Structure:

source
  ↓
network
  ↓
sink

Capacities represent:

Bandwidth
Road capacity
Pipeline throughput
Production limits
Transportation limits

Example

Internet routing:

Data Center A
    ↓
Routers
    ↓
Data Center B

Maximum flow measures maximum throughput.

Minimum cut identifies bottlenecks.

Pattern 4: Selection Problems

Some problems ask:

Which items should we choose?

rather than:

How much flow can we send?

Use a min-cut formulation.

Structure:

source
  ↓
profitable items

dependency edges

costly items
  ↓
sink

Example

Projects:

Project	Value
API	+10
Database	-4
Analytics	+8

Dependency:

Analytics requires API

Infinite-capacity dependency edges enforce valid selections.

The minimum cut yields the optimal project portfolio.

Pattern 5: Time Expansion

Scheduling and planning often involve time.

Create a copy of important vertices for each time step.

Structure:

Resource@t0
Resource@t1
Resource@t2
...

Edges represent:

Waiting
Moving
Processing
Starting jobs
Completing jobs

Example

Train scheduling:

Station A @ 8:00
Station A @ 9:00
Station A @ 10:00

Flow through time-expanded nodes represents train movement.

Pattern 6: Resource Allocation

Resources have limited capacity.

Consumers require resources.

Structure:

source
  ↓
resources
  ↓
tasks
  ↓
sink

Example

Cloud allocation:

Resource	Capacity
CPU	100
Memory	200
GPU	10

Applications consume combinations of resources.

Flow determines feasible allocation.

Pattern 7: Disjoint Paths

Reliability often requires multiple independent routes.

Edge-Disjoint

Assign:

capacity = 1

to every edge.

Maximum flow equals:

maximum edge-disjoint paths

Vertex-Disjoint

Split every internal vertex:

v_in -> v_out
capacity = 1

Maximum flow equals:

maximum vertex-disjoint paths

Example

Network resilience:

How many independent routes
exist between two sites?

Use disjoint-path modeling.

Pattern 8: Lower-Bound Feasibility

Sometimes the problem contains minimum requirements.

Example:

At least 3 workers
must cover night shift.

Standard capacities are insufficient.

Use:

lower ≤ flow ≤ capacity

Then apply the circulation transformation.

Example

Shift:

Night
lower = 3
capacity = 5

This guarantees minimum coverage.

Pattern 9: Cost Optimization

Not all feasible solutions are equally good.

Attach costs to edges.

Then use minimum-cost flow.

Example

Worker preferences:

Assignment	Cost
Alice → Morning	1
Alice → Night	8

The algorithm minimizes total dissatisfaction.

Other cost interpretations include:

Distance
Fuel
Time
Risk
Penalties
Energy consumption

Pattern 10: Partitioning

Some problems require dividing objects into groups.

Use graph cuts.

Structure:

source
  ↓
objects
  ↓
sink

Edge capacities encode:

Similarity
Preference
Classification confidence

Example

Image segmentation:

foreground
vs
background

The minimum cut determines the partition.

Recognizing a Flow Problem

Ask these questions.

Is Something Being Assigned?

Examples:

worker -> job
student -> course
driver -> route

Think matching or assignment.

Is Something Being Transported?

Examples:

water
traffic
packets
goods

Think maximum flow.

Are There Capacities?

Examples:

at most
capacity
limit
quota

Flow models naturally represent these.

Are There Minimum Requirements?

Examples:

at least
minimum staffing
minimum throughput

Think lower bounds and circulation.

Are There Costs?

Examples:

minimize distance
minimize expense
maximize profit

Think minimum-cost flow or min-cut.

Are There Dependencies?

Examples:

requires
depends on
must include

Think project-selection cuts.

Combining Patterns

Real problems often combine several templates.

Example: Hospital Scheduling

Requirements:

Nurses assigned to shifts.
Minimum staffing.
Maximum workload.
Preference costs.

Model:

assignment
+
lower bounds
+
cost optimization

Example: Delivery Network

Requirements:

Vehicle capacities.
Time windows.
Transportation costs.

Model:

routing
+
time expansion
+
minimum-cost flow

Example: Cloud Resource Planning

Requirements:

Resource limits.
Application placement.
Redundancy.

Model:

resource allocation
+
disjoint paths
+
cost optimization

When Flow Is the Wrong Tool

Flow is powerful, but not universal.

Warning signs:

Complex Boolean Logic

Example:

(A and B)
or
(C and not D)

Flow struggles with arbitrary logical formulas.

Long Sequential Dependencies

Example:

job ordering
machine sequencing
traveling salesman constraints

These often require dynamic programming, SAT, constraint programming, or integer programming.

Global Nonlinear Objectives

Example:

variance
quadratic penalties
nonlinear utilities

Standard flow models assume linear objectives.

A Modeling Checklist

When reading a problem:

Identify resources.
Identify consumers.
Identify capacities.
Identify minimum requirements.
Identify costs.
Identify dependencies.
Determine whether time matters.
Determine whether reliability matters.
Decide whether the problem is feasibility or optimization.
Select the simplest flow template that fits.

Discussion

The hardest part of network flow is rarely the algorithm. Dinic, Hopcroft-Karp, Hungarian, and min-cost flow are well understood. The real challenge is modeling.

Experienced practitioners spend most of their effort converting domain constraints into graph structure. Once the graph accurately represents the problem, the algorithm is often straightforward.

This is why network flow remains one of the most important topics in algorithm design. It provides a common language for scheduling, allocation, routing, matching, planning, optimization, and partitioning.

Takeaway

Most practical flow applications are instances of a small set of modeling patterns: supply-demand networks, assignment graphs, routing networks, resource allocation systems, lower-bound feasibility models, cost-optimization networks, and graph cuts.

When confronted with a new optimization problem, focus first on identifying the pattern. Once the structure is recognized, the appropriate flow formulation and algorithm usually become clear.