Min Cost Flow Slotting › Example

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.

There is another 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:

$$\begin{aligned} \text{Total Cost} &= \sum_{(i,j) \in E} c_{ij} \cdot x_{ij} \\ &= 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} \\ &= 4 \cdot 10 + 6 \cdot 0 + 2 \cdot 10 + 3 \cdot 0 + 1 \cdot 0 \\ &= 40 + 0 + 20 + 0 + 0 \\ &= 60 \text{ cost units} \end{aligned}$$

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.