Minimum Cost Flow Slotting: Complete Guide to Network Flow Optimization & Resource Allocation

The Minimum Cost flow (MCF) problem finds the most cost-effective way to transport a specified amount of flow through a network. This problem appears in many real-world applications, from supply chain logistics and telecommunications routing to resource allocation and scheduling. The MCF problem can model complex network structures while remaining computationally tractable, making it useful in operations research and optimization.

In the context of slotting, the MCF problem helps determine optimal resource allocation across time slots, capacity constraints, and cost structures. For example, in workforce scheduling, we might need to assign employees to different time slots while minimizing costs and respecting availability constraints. In manufacturing, we might need to schedule production across different machines and time periods while minimizing operational costs. The MCF formulation provides a mathematically rigorous framework for solving these allocation problems efficiently.

Unlike simpler optimization approaches that might use greedy heuristics or linear programming, the MCF problem can handle complex network structures with multiple sources, sinks, and intermediate nodes. This makes it particularly valuable for real-world problems where resources flow through multiple stages or where there are complex interdependencies between different allocation decisions. The network structure also allows for natural modeling of capacity constraints, time windows, and cost structures that reflect real operational constraints.

AdvantagesLink Copied

The Minimum Cost flow approach offers several advantages for slotting problems. First, it provides a mathematically rigorous framework that guarantees optimal solutions when feasible solutions exist. Unlike heuristic approaches that might find good but suboptimal solutions, the MCF formulation ensures that we find the optimal allocation of resources across the network. This optimality guarantee matters in applications where even small improvements in efficiency can lead to significant cost savings.

Second, the MCF problem is computationally efficient and can handle large-scale problems with thousands of nodes and edges. Modern optimization algorithms, particularly those based on network flow theory, can solve MCF problems very quickly, often in milliseconds or seconds even for complex networks. This computational efficiency makes the approach suitable for real-time applications where decisions need to be made quickly, such as dynamic resource allocation or real-time scheduling systems.

Third, the network structure of the MCF problem provides excellent modeling flexibility. We can easily incorporate various types of constraints, including capacity limits, time windows, precedence relationships, and cost structures. The network representation also makes it intuitive to understand and visualize the problem structure, which is valuable for both model development and communication with stakeholders who need to understand the optimization logic.

DisadvantagesLink Copied

Despite its strengths, the Minimum Cost flow approach has some limitations that practitioners should consider. The most significant limitation is that it requires the problem to be formulated as a network flow problem, which may not always be natural or intuitive for all slotting applications. Some real-world constraints, such as complex precedence relationships or non-linear cost structures, may be difficult to model within the network flow framework.

Another limitation is that the MCF problem assumes that flow can be split and combined freely at nodes, which may not always reflect real-world constraints. For example, in workforce scheduling, we might need to ensure that employees work complete shifts rather than being split across multiple time periods. While these constraints can sometimes be handled through problem transformation, they can make the formulation more complex and less intuitive.

Finally, the MCF approach may struggle with problems that have very tight constraint sets or where finding any feasible solution is difficult. In such cases, the solver might need to explore a large portion of the solution space, leading to longer computation times. Additionally, if the problem is infeasible, the MCF solver will simply report that no solution exists, without providing guidance on which constraints might be relaxed to achieve feasibility.

To solve the Minimum Cost flow problem mathematically, we need to translate our intuitive understanding of networks, flows, and costs into a precise mathematical framework. This process reveals why each component is needed and how they work together to create a solvable optimization problem.

Before diving into mathematical notation, let's clarify what we're trying to achieve. Imagine you're managing a supply chain: you have factories producing goods, warehouses storing them, and markets demanding them. You need to route products through this network in a way that:

1. Satisfies all demands - Every market gets exactly what it needs
2. Respects all capacities - You can't ship more than your trucks, pipelines, or facilities can handle
3. Minimizes total cost - Among all feasible routing strategies, you want the cheapest one

The Minimum Cost flow problem formalizes this intuition. But to solve it mathematically, we need to be precise about what "network," "flow," and "cost" actually mean in mathematical terms.

The first step is representing our problem as a directed graph, a mathematical structure that captures the relationships in our system. Graphs naturally model connections: which locations can send to which other locations, which resources can flow through which pathways.

We define our network as a directed graph $G = (V, E)$ where:

• $G$: The directed graph representing our network
• $V$: The set of nodes (vertices) - these represent locations, resources, time periods, or any entities between which flow can occur
• $E$: The set of directed edges (arcs) - these represent the pathways through which flow can travel, with direction indicating the allowed flow direction

The directed nature matters: a factory can ship to a warehouse, but the reverse might not make physical sense. The graph structure captures these one-way relationships naturally.

Not all nodes play the same role in our network. Some nodes are sources - they generate flow (like factories producing goods). Others are sinks - they consume flow (like markets demanding products). Still others are intermediate nodes - they neither generate nor consume, but simply pass flow through (like warehouses or distribution centers).

We capture this distinction mathematically through a supply value $b_i$ for each node $i \in V$:

where:

• $i$: Node index, where $i \in V$ (ranges over all nodes in the network)
• $b_i$: Supply value at node $i$ (units of flow)
  • If $b_i > 0$: Node $i$ is a supply node (source) that generates $b_i$ units of flow
  • If $b_i < 0$: Node $i$ is a demand node (sink) that requires $|b_i|$ units of flow
  • If $b_i = 0$: Node $i$ is a transshipment node that neither generates nor consumes net flow

Why do we need this distinction? Because all flow needs to originate somewhere and terminate somewhere. The supply values tell us exactly how much flow needs to enter the network (from sources) and how much needs to exit (to sinks). This is the mathematical way of saying "we need to satisfy all demands using available supplies."

Just as nodes have different roles, edges have different properties. Each edge $(i,j) \in E$ represents a pathway from node $i$ to node $j$, and we need to describe two key properties:

where:

• $(i,j)$: Directed edge from node $i$ to node $j$, where $(i,j) \in E$
• $i$: Source node of the edge (where flow originates)
• $j$: Destination node of the edge (where flow terminates)

1. Capacity $u_{ij}$: The maximum amount of flow that can pass through edge $(i,j)$. This represents physical or operational limits - a truck can only carry so much, a pipeline has a maximum throughput, a worker can only handle so many tasks per hour. Units: same as flow units.

2. Cost $c_{ij}$: The cost per unit of flow sent through edge $(i,j)$. This captures the expense, time, or penalty associated with using this particular pathway. Units: cost per unit of flow.

Why do we need both? Capacity constraints prevent us from making physically infeasible allocations (you can't ship 1000 units through a pipeline that can only handle 100). Cost values allow us to distinguish between different feasible pathways. Even if multiple routes can handle the flow, we want to choose the cheapest one.

Now we come to the heart of the optimization problem: what decisions are we making? In the Minimum Cost flow problem, our decision is simple but powerful: for each edge in the network, we need to decide how much flow to send through it.

We represent these decisions as decision variables $x_{ij}$ for each edge $(i,j) \in E$:

$x_{ij} \geq 0 \quad \forall (i,j) \in E$

where:

• $x_{ij}$: Decision variable representing the amount of flow sent through edge $(i,j)$ (units of flow)
• $(i,j)$: Edge from node $i$ to node $j$, where $(i,j) \in E$
• $\forall$: "For all" - this constraint applies to every edge in the network

The non-negativity constraint ($x_{ij} \geq 0$) is needed because flow can only go in the direction of the edge. If we wanted to allow reverse flow, we would need a separate edge pointing in the opposite direction.

These decision variables are what the optimization algorithm will determine. Once we've set up our constraints and objective function, the solver will find the values of all $x_{ij}$ that minimize cost while satisfying all constraints.

Our goal is to find the cheapest way to route flow through the network. But what does "cheapest" mean mathematically?

The total cost of a solution is the sum of costs across all edges, where each edge's contribution is its unit cost multiplied by the amount of flow we send through it. This gives us our objective function:

$\min \sum_{(i,j) \in E} c_{ij} \cdot x_{ij}$

where:

• $\min$: Minimization operator - we seek to minimize the total cost
• $\sum_{(i,j) \in E}$: Sum over all edges $(i,j)$ in the edge set $E$
• $c_{ij}$: Unit cost per flow on edge $(i,j)$ (cost per unit of flow)
• $x_{ij}$: Flow amount on edge $(i,j)$ (units of flow)
• $c_{ij} \cdot x_{ij}$: Total cost contribution from edge $(i,j)$ (cost units)

This formula assumes that costs are linear in the amount of flow. Sending 10 units through an edge costs exactly 10 times as much as sending 1 unit. This linearity makes the problem computationally tractable, and it's a reasonable assumption for many real-world scenarios (though not all; some problems require non-linear cost functions, which would need different solution approaches).

The minimization operator tells us we're seeking the solution that makes this sum as small as possible, subject to all the constraints we're about to define.

We need to ensure that flow is conserved throughout the network. Flow doesn't magically appear or disappear at nodes. This conservation principle expresses physical reality: what goes into a node needs to come out (or be consumed), and what comes out needs to have come in (or been generated).

For each node $i \in V$, we write the flow conservation constraint:

$\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i$

Let's visualize what this means at a single node:

This visualization shows how flow conservation works at a single node. Blue arrows represent flow entering the node, green arrows represent flow leaving the node. The equation Flow Out - Flow In = Supply must hold for each node type.

where:

• $i$: Node index, where $i \in V$ (this constraint applies to every node)
• $\sum_{j: (i,j) \in E} x_{ij}$: Sum of all flow leaving node $i$ (flow on edges that start at $i$)
  • $j$: Index over all nodes $j$ such that edge $(i,j)$ exists
  • $x_{ij}$: Flow amount on edge $(i,j)$ leaving node $i$
• $\sum_{j: (j,i) \in E} x_{ji}$: Sum of all flow entering node $i$ (flow on edges that end at $i$)
  • $j$: Index over all nodes $j$ such that edge $(j,i)$ exists
  • $x_{ji}$: Flow amount on edge $(j,i)$ entering node $i$
• $b_i$: Supply value at node $i$ (positive for sources, negative for sinks, zero for transshipment)

Let's break this down carefully:

• The first sum $\sum_{j: (i,j) \in E} x_{ij}$ represents all flow leaving node $i$ (flow on edges that start at $i$)
• The second sum $\sum_{j: (j,i) \in E} x_{ji}$ represents all flow entering node $i$ (flow on edges that end at $i$)
• Their difference equals $b_i$, the supply at node $i$

Why is this the right constraint? Consider what happens at different types of nodes:

• Supply nodes ($b_i > 0$): More flow leaves than enters. The difference equals the supply generated at this node. For example, if a factory generates 10 units, then $x_{out} - x_{in} = 10$, meaning 10 more units leave than enter.

• Demand nodes ($b_i < 0$): More flow enters than leaves. The difference is negative, matching the negative demand. For example, if a market needs 10 units, then $x_{out} - x_{in} = -10$, meaning 10 more units enter than leave.

• Transshipment nodes ($b_i = 0$): Flow in equals flow out. These nodes simply pass flow through without generating or consuming any net amount.

This single constraint type elegantly handles all three node types, ensuring that flow is properly balanced throughout the entire network. Without this constraint, we could have solutions where flow appears or disappears at nodes, which would be physically meaningless.

While flow conservation ensures flow is balanced, it doesn't prevent us from trying to send more flow through an edge than it can physically handle. We need capacity constraints to enforce the limits we defined for each edge:

$0 \leq x_{ij} \leq u_{ij} \quad \forall (i,j) \in E$

where:

• $x_{ij}$: Flow amount on edge $(i,j)$ (units of flow)
• $u_{ij}$: Capacity (maximum flow) allowed on edge $(i,j)$ (units of flow)
• $\forall (i,j) \in E$: "For all edges" - this constraint applies to every edge in the network
• $0 \leq x_{ij}$: Non-negativity constraint (flow cannot be negative)
• $x_{ij} \leq u_{ij}$: Capacity constraint (flow cannot exceed the edge capacity)

This constraint specifies that the flow on edge $(i,j)$ should be:

• At least zero (we already had this from the non-negativity of decision variables)
• At most $u_{ij}$ (the capacity limit we defined for this edge)

Why is this necessary? Without capacity constraints, the optimal solution might try to route all flow through a single cheap edge, even if that edge can only handle a fraction of the required flow. Capacity constraints force the solver to distribute flow across multiple pathways, respecting the physical realities of the network.

Together with flow conservation, capacity constraints ensure that our solution is not just mathematically valid, but also physically feasible.

Now we can assemble all these pieces into the complete Minimum Cost flow problem:

Objective Function: $\min \sum_{(i,j) \in E} c_{ij} \cdot x_{ij}$

Subject to:

Flow Conservation Constraints: $\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i \quad \forall i \in V$

Capacity Constraints: $0 \leq x_{ij} \leq u_{ij} \quad \forall (i,j) \in E$

Variable Definitions:

• $G = (V, E)$: Directed graph with node set $V$ and edge set $E$
• $i, j$: Node indices, where $i, j \in V$
• $(i,j)$: Directed edge from node $i$ to node $j$, where $(i,j) \in E$
• $x_{ij}$: Decision variable - flow amount on edge $(i,j)$ (units of flow)
• $c_{ij}$: Unit cost per flow on edge $(i,j)$ (cost per unit of flow)
• $u_{ij}$: Capacity (maximum flow) on edge $(i,j)$ (units of flow)
• $b_i$: Supply value at node $i$ (positive for sources, negative for sinks, zero for transshipment)
• $\forall$: "For all" quantifier

This formulation is a linear programming problem, a special type of optimization problem where both the objective function and all constraints are linear in the decision variables. This linearity allows us to use highly efficient specialized algorithms that can solve even large-scale problems quickly.

The Minimum Cost flow formulation has several beautiful mathematical properties that make it both theoretically elegant and practically useful:

1. Linear Programming Structure: The MCF problem is a special case of linear programming with a particularly nice structure. The network topology creates a constraint matrix with special properties (totally unimodular), which enables the use of highly efficient specialized algorithms that are much faster than general-purpose linear programming solvers.

2. Integrality Property: If all supplies $b_i$, demands, and capacities $u_{ij}$ are integers, then there exists an optimal solution where all flows $x_{ij}$ are also integers. This matters for practical applications where fractional allocations don't make sense; you can't ship 3.7 trucks or assign 2.3 workers to a shift. The integrality property guarantees that we'll get whole-number solutions automatically, without needing to add integer constraints (which would make the problem much harder to solve).

3. Duality and Economic Interpretation: The MCF problem has a natural dual interpretation involving node potentials (often interpreted as prices). The dual variables tell us the marginal value of increasing supply or capacity at different nodes, providing valuable economic insights. If the dual variable at a demand node is high, it means that location is a bottleneck - increasing supply there would significantly reduce total cost.

These properties aren't just mathematical curiosities - they're what make the Minimum Cost flow problem both solvable and interpretable in real-world applications. The linear structure enables fast computation, the integrality property ensures practical solutions, and the duality provides insights for decision-makers.

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.

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

Let's work through a concrete example that brings together all the concepts we've discussed. We'll see how the mathematical formulation translates into a real optimization problem, and we'll trace through the logic to understand why the optimal solution takes the form it does.

Imagine you're managing a supply chain with the following structure:

• Factory (Node 0): Produces 10 units of product (a supply node with $b_0 = 10$)
• Warehouse (Node 1): A storage facility that neither produces nor consumes (a transshipment node with $b_1 = 0$)
• Distribution Center (Node 2): Another intermediate facility (a transshipment node with $b_2 = 0$)
• Market (Node 3): Requires exactly 10 units to satisfy demand (a demand node with $b_3 = -10$)

The network has five possible shipping routes, each with different capacities and costs:

• Factory → Warehouse: Can handle up to 15 units, costs 4 per unit
• Factory → Distribution: Can handle up to 8 units, costs 6 per unit
• Warehouse → Market: Can handle up to 10 units, costs 2 per unit
• Distribution → Market: Can handle up to 12 units, costs 3 per unit
• Warehouse → Distribution: Can handle up to 5 units, costs 1 per unit (a shortcut route)

Notice that we have multiple pathways from the factory to the market. Our goal is to find the cheapest way to route all 10 units from the factory to the market while respecting capacity limits.

Here's a visual representation of this network:

This diagram shows the network structure we'll analyze. The Factory (node 0) supplies 10 units, the Market (node 3) demands 10 units, and the Warehouse and Distribution Center are transshipment nodes. Each edge is labeled with its unit cost and capacity limit.

Step 1: Define Decision Variables

We need to decide how much flow to send through each of the five edges:

• $x_{01}$ = flow from Factory to Warehouse
• $x_{02}$ = flow from Factory to Distribution
• $x_{13}$ = flow from Warehouse to Market
• $x_{23}$ = flow from Distribution to Market
• $x_{12}$ = flow from Warehouse to Distribution

Each of these should be non-negative (we can't send negative flow), and we'll determine their optimal values through optimization.

Step 2: Construct the Objective Function

Our goal is to minimize total cost. The objective function follows the general form: $\min \sum_{(i,j) \in E} c_{ij} \cdot x_{ij}$

For our specific network, this expands to: $\min c_{01} \cdot x_{01} + c_{02} \cdot x_{02} + c_{13} \cdot x_{13} + c_{23} \cdot x_{23} + c_{12} \cdot x_{12}$

Substituting the unit costs: $\min 4x_{01} + 6x_{02} + 2x_{13} + 3x_{23} + 1x_{12}$

where:

• $c_{01} = 4$: Unit cost for Factory → Warehouse
• $c_{02} = 6$: Unit cost for Factory → Distribution
• $c_{13} = 2$: Unit cost for Warehouse → Market
• $c_{23} = 3$: Unit cost for Distribution → Market
• $c_{12} = 1$: Unit cost for Warehouse → Distribution

Each term represents the cost contribution from one edge: the unit cost multiplied by the flow amount. Notice that the Warehouse → Distribution route ($x_{12}$) has the lowest unit cost (1), which might make it attractive if we can use it effectively.

Step 3: Apply Flow Conservation Constraints

Flow conservation ensures that flow is balanced at each node. For each node $i$, we apply the general form: $\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i$

Let's work through each node:

• Factory (Node 0): This is a supply node with $b_0 = 10$. Applying the flow conservation constraint: $\sum_{j: (0,j) \in E} x_{0j} - \sum_{j: (j,0) \in E} x_{j0} = x_{01} + x_{02} - 0 = 10 = b_0$

  Simplified: $x_{01} + x_{02} = 10$

  This says: all flow leaving the factory (the two outgoing edges) must equal the 10 units the factory produces. There are no incoming edges to the factory, so this is simply a supply constraint.

• Warehouse (Node 1): This is a transshipment node with $b_1 = 0$. Applying the flow conservation constraint: $\sum_{j: (1,j) \in E} x_{1j} - \sum_{j: (j,1) \in E} x_{j1} = (x_{13} + x_{12}) - x_{01} = 0 = b_1$

  Simplified: $x_{13} + x_{12} - x_{01} = 0$, or equivalently $x_{01} = x_{13} + x_{12}$

  This says: all flow entering the warehouse (from the factory) must equal all flow leaving (to the market and to the distribution center). The warehouse neither creates nor destroys flow.

• Distribution (Node 2): This is also a transshipment node with $b_2 = 0$. Applying the flow conservation constraint: $\sum_{j: (2,j) \in E} x_{2j} - \sum_{j: (j,2) \in E} x_{j2} = x_{23} - (x_{02} + x_{12}) = 0 = b_2$

  Simplified: $x_{23} - x_{02} - x_{12} = 0$, or equivalently $x_{02} + x_{12} = x_{23}$

  This says: flow entering the distribution center (from the factory and from the warehouse) must equal flow leaving (to the market).

• Market (Node 3): This is a demand node with $b_3 = -10$. Applying the flow conservation constraint: $\sum_{j: (3,j) \in E} x_{3j} - \sum_{j: (j,3) \in E} x_{j3} = 0 - (x_{13} + x_{23}) = -10 = b_3$

  Simplified: $-x_{13} - x_{23} = -10$, or equivalently $x_{13} + x_{23} = 10$

  This says: all flow entering the market (from the warehouse and from the distribution center) must equal the 10 units of demand.

Step 4: Apply Capacity Constraints

Each edge has a maximum capacity that cannot be exceeded. The general form is: $0 \leq x_{ij} \leq u_{ij} \quad \forall (i,j) \in E$

For our specific network, this gives us:

• $0 \leq x_{01} \leq u_{01} = 15$ (Factory → Warehouse)
• $0 \leq x_{02} \leq u_{02} = 8$ (Factory → Distribution)
• $0 \leq x_{13} \leq u_{13} = 10$ (Warehouse → Market)
• $0 \leq x_{23} \leq u_{23} = 12$ (Distribution → Market)
• $0 \leq x_{12} \leq u_{12} = 5$ (Warehouse → Distribution)

where:

• $u_{01} = 15$: Capacity of Factory → Warehouse edge
• $u_{02} = 8$: Capacity of Factory → Distribution edge
• $u_{13} = 10$: Capacity of Warehouse → Market edge
• $u_{23} = 12$: Capacity of Distribution → Market edge
• $u_{12} = 5$: Capacity of Warehouse → Distribution edge

These constraints prevent us from overloading any shipping route.

Now we have a complete optimization problem. Let's reason through what the optimal solution should look like, then verify with computation.

Intuitive Reasoning:

The cheapest route from Factory to Market is Factory → Warehouse → Market, with total cost $4 + 2 = 6$ per unit. However, the Warehouse → Market edge has capacity 10, which is exactly our demand. So we could send all 10 units this way... but wait, let's check if there's a better strategy.

Actually, we have an interesting option: the Warehouse → Distribution route costs only 1 per unit, and Distribution → Market costs 3 per unit. So Factory → Warehouse → Distribution → Market costs $4 + 1 + 3 = 8$ per unit, which is more expensive than the direct Warehouse → Market route.

However, the Factory → Distribution route costs 6 per unit, and Distribution → Market costs 3 per unit, for a total of $6 + 3 = 9$ per unit. This is the most expensive direct path.

The optimal strategy balances these trade-offs. Since Warehouse → Market has capacity 10 (exactly our demand), we could use it fully. But we also need to consider whether splitting flow might be beneficial.

Finding the Optimal Solution:

Now we have a complete optimization problem. Let's think through the solution strategy:

Strategy 1: Use the cheapest path exclusively

The path Factory → Warehouse → Market has total cost per unit calculated as: $c_{01} + c_{13} = 4 + 2 = 6 \text{ cost units per flow unit}$

If we send all 10 units this way:

• $x_{01} = 10$ (within capacity $u_{01} = 15$)
• $x_{13} = 10$ (exactly at capacity $u_{13} = 10$)

Total cost calculation: $\text{Total Cost} = c_{01} \cdot x_{01} + c_{13} \cdot x_{13} = 4 \cdot 10 + 2 \cdot 10 = 40 + 20 = 60 \text{ cost units}$

This is feasible and seems attractive. But is it optimal?

Strategy 2: Split between two direct paths

We could send some units Factory → Warehouse → Market and some Factory → Distribution → Market:

• Factory → Warehouse → Market: cost per unit = $c_{01} + c_{13} = 4 + 2 = 6$ cost units per flow unit
• Factory → Distribution → Market: cost per unit = $c_{02} + c_{23} = 6 + 3 = 9$ cost units per flow unit

Since the first path is cheaper, we'd want to use it to full capacity (10 units), leaving 0 for the second path. This gives us Strategy 1 again.

Strategy 3: Use the shortcut route

What about using the Warehouse → Distribution shortcut? The path Factory → Warehouse → Distribution → Market has cost per unit: $c_{01} + c_{12} + c_{23} = 4 + 1 + 3 = 8 \text{ cost units per flow unit}$

This is more expensive than the direct Warehouse → Market route (cost 6 per unit). So this doesn't help.

The Optimal Solution:

By solving the optimization problem (either algebraically or using a solver), we find that Strategy 1 is optimal:

• $x_{01} = 10$ (all 10 units: Factory → Warehouse)
• $x_{13} = 10$ (all 10 units: Warehouse → Market)
• $x_{02} = 0$, $x_{23} = 0$, $x_{12} = 0$ (unused routes)

Total Cost Calculation:

The total cost is computed using the objective function:

Why This Makes Sense:

This solution is optimal because:

1. The cheapest path (Factory → Warehouse → Market) has sufficient capacity to handle all demand
2. Using it exclusively minimizes cost at 6 per unit
3. All alternative paths cost more (9 per unit for Factory → Distribution → Market, 8 per unit if we use the shortcut)

The key insight is that when the cheapest path has sufficient capacity, we should use it exclusively. The solver would only split flow across multiple paths if:

• No single path has enough capacity for all demand, OR
• There are additional constraints (like minimum flow requirements) that force splitting, OR
• The cost structure makes splitting beneficial (which doesn't happen in this example)

Verifying the Constraints:

Let's verify this solution satisfies all constraints:

Flow Conservation Constraints:

For each node $i$, we verify that $\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = b_i$:

• Factory (Node 0): Flow out - Flow in = Supply $\sum_{j: (0,j) \in E} x_{0j} - \sum_{j: (j,0) \in E} x_{j0} = x_{01} + x_{02} - 0 = 10 + 0 = 10 = b_0$

• Warehouse (Node 1): Flow out - Flow in = Supply $\sum_{j: (1,j) \in E} x_{1j} - \sum_{j: (j,1) \in E} x_{j1} = x_{13} + x_{12} - x_{01} = 10 + 0 - 10 = 0 = b_1$

• Distribution (Node 2): Flow out - Flow in = Supply $\sum_{j: (2,j) \in E} x_{2j} - \sum_{j: (j,2) \in E} x_{j2} = x_{23} - (x_{02} + x_{12}) = 0 - (0 + 0) = 0 = b_2$

• Market (Node 3): Flow out - Flow in = Supply $\sum_{j: (3,j) \in E} x_{3j} - \sum_{j: (j,3) \in E} x_{j3} = 0 - (x_{13} + x_{23}) = 0 - (10 + 0) = -10 = b_3$

Capacity Constraints:

For each edge $(i,j)$, we verify that $0 \leq x_{ij} \leq u_{ij}$:

• $x_{01} = 10$: $0 \leq 10 \leq 15 = u_{01}$
• $x_{02} = 0$: $0 \leq 0 \leq 8 = u_{02}$
• $x_{13} = 10$: $0 \leq 10 \leq 10 = u_{13}$ (at capacity)
• $x_{23} = 0$: $0 \leq 0 \leq 12 = u_{23}$
• $x_{12} = 0$: $0 \leq 0 \leq 5 = u_{12}$

All constraints are satisfied, and we've achieved the minimum possible cost. This example illustrates how the mathematical formulation guides us to the optimal solution systematically, even when the problem seems simple enough to solve by intuition.

Now that we understand the mathematical formulation, let's see how to implement it in practice. We'll use OR-Tools, Google's open-source optimization library, which provides efficient solvers specifically designed for network flow problems.

OR-Tools is an excellent choice for Minimum Cost flow problems because:

1. Specialized Algorithms: The SimpleMinCostFlow solver uses highly optimized algorithms (like the successive shortest path algorithm or cost scaling) that are much faster than general-purpose linear programming solvers for network flow problems.

2. Ease of Use: The API directly maps to our mathematical formulation - we specify nodes, edges, capacities, costs, and supplies, and the solver handles the rest.

3. Robustness: OR-Tools has been battle-tested on real-world problems and handles edge cases (infeasible problems, numerical issues) gracefully.

4. Open Source: Free to use and well-documented, making it accessible for both learning and production applications.

The key insight is that our mathematical formulation translates directly into OR-Tools API calls:

• Edges $(i,j) \in E$ → add_arc_with_capacity_and_unit_cost(start_node, end_node, capacity, cost)
• Node Supplies $b_i$ → set_node_supply(node, supply)
• Decision Variables $x_{ij}$ → Automatically handled by the solver (we query the results)
• Objective Function → Automatically minimized by the solver
• Constraints → Automatically enforced by the solver

The solver takes care of all the constraint enforcement and optimization - we just need to specify the problem structure.

Let's create a function that encapsulates the solution process, making it easy to solve different MCF problems. This function will handle network construction, solving, and solution extraction:

Now let's display the results from the supply chain example:

The solver found an optimal solution with a total cost of 60 cost units. This matches our mathematical analysis from the Example section, where we determined that routing all 10 units through Factory → Warehouse → Market (cost 6 per unit) is optimal. The solution shows that edges (0,1) and (1,3) carry the full flow of 10 units each, while other edges remain unused. This makes operational sense: the cheapest path has sufficient capacity to handle all demand, so there's no need to split flow across multiple routes. The unused edges (0,2), (1,2), and (2,3) have zero flow, indicating they're not part of the optimal solution.

The power of the Minimum Cost flow formulation becomes even clearer when we tackle more complex problems. Let's consider a time slotting problem where we need to allocate resources across multiple time periods to complete various tasks. This demonstrates how MCF can model problems with multiple stages and complex routing requirements.

The key insight is that we can model time as a dimension in our network: resources flow through time slots, and then through tasks, creating a multi-stage network structure.

Now let's display the results from the time slotting example:

The solver found an optimal allocation that routes resources through time slots to tasks while minimizing total cost. The solution balances multiple competing factors: resource capacity limits prevent over-allocation, time slot availability constrains when work can be done, and task requirements ensure all work is completed. Notice that the cost structure (increasing costs for later time slots) encourages the solver to prefer earlier time slots when possible, which aligns with operational preferences for completing work sooner rather than later. The total cost reflects the trade-offs between these constraints, and the allocation shows how resources are efficiently distributed across the network to achieve this optimal balance.

Sometimes it's useful to work directly with the OR-Tools solver object rather than using a wrapper function. This gives you more control and helps you understand exactly how the solver API maps to our mathematical formulation. Let's see how to build a network step-by-step:

Now let's display the results from the manual network construction:

The solver successfully found an optimal solution for this network. The total cost represents the minimum achievable cost given the network structure, capacities, and unit costs. Each arc's flow value shows how the solver allocated flow to minimize total cost while respecting capacity constraints. Arcs with zero flow indicate that those edges are not part of the optimal solution. The solver determined that routing flow through alternative paths is more cost-effective. This demonstrates how the MCF solver automatically identifies the most efficient routing strategy without requiring manual path selection.

Below are the main parameters and methods that affect how Minimum Cost Flow problems are solved using OR-Tools.

Key ParametersLink Copied

The SimpleMinCostFlow solver in OR-Tools doesn't expose many configurable parameters directly, as it uses specialized algorithms optimized for network flow problems. However, the problem structure itself is defined by several key parameters:

• start_nodes: List of starting nodes for each arc (the "i" in edge $(i,j)$). Each element corresponds to one edge in the network. Should have the same length as end_nodes, capacities, and unit_costs.

• end_nodes: List of ending nodes for each arc (the "j" in edge $(i,j)$). Together with start_nodes, this defines the network topology. Node indices should be non-negative integers starting from 0.

• capacities: List of capacity values $u_{ij}$ for each arc (maximum flow allowed). Should be non-negative. Use realistic values based on actual operational constraints rather than arbitrarily large numbers. Values should be in the same units as flow variables.

• unit_costs: List of unit cost values $c_{ij}$ for each arc (cost per unit of flow). Can be any real number (positive, negative, or zero). Negative costs can model revenue or benefits. Ensure all costs use consistent units (cost per flow unit).

• supplies: List of supply values $b_i$ for each node. Positive values represent sources (supply nodes), negative values represent sinks (demand nodes), and zero represents transshipment nodes. The sum of all positive supplies should equal the absolute sum of all negative demands for the problem to be feasible.