Min Cost Flow Slotting › Formula

To solve the Minimum Cost flow problem mathematically, we need to express the network and its flows in a precise framework that accounts for cost. 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 precise mathematical definitions of "network," "flow," and "cost."

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. 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 mathematically valid and 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. 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.