๐ Problem Overview
The Production Lot Size Problem (also known as the Capacitated Lot Sizing Problem, CLSP) asks: How many units of each product should we produce in each period to minimize total costs, while satisfying demand and not exceeding production capacity?
When lot sizes must be integers (you canโt produce half a unit), this becomes a Mixed-Integer Programming (MIP) problem โ significantly harder than its continuous cousin.
๐งฎ Mathematical Formulation
Sets & Indices:
- $i \in {1, \ldots, N}$: products
- $t \in {1, \ldots, T}$: time periods
Decision Variables:
- $x_{it} \in \mathbb{Z}_{\geq 0}$: production quantity of product $i$ in period $t$ (integer)
- $y_{it} \in {0, 1}$: setup indicator (1 if product $i$ is produced in period $t$)
- $s_{it} \geq 0$: inventory of product $i$ at end of period $t$
Parameters:
- $d_{it}$: demand for product $i$ in period $t$
- $p_i$: unit production cost for product $i$
- $h_i$: unit holding cost per period for product $i$
- $f_i$: fixed setup cost for product $i$
- $c_t$: capacity available in period $t$
- $a_i$: capacity consumed per unit of product $i$
- $M$: big-M constant
Objective โ Minimize total cost:
$$\min \sum_{i=1}^{N} \sum_{t=1}^{T} \left( p_i x_{it} + h_i s_{it} + f_i y_{it} \right)$$
Subject to:
Inventory balance:
$$s_{i,t-1} + x_{it} - s_{it} = d_{it} \quad \forall i, t$$
Capacity constraint:
$$\sum_{i=1}^{N} a_i x_{it} \leq c_t \quad \forall t$$
Setup linkage (Big-M):
$$x_{it} \leq M \cdot y_{it} \quad \forall i, t$$
Integrality & non-negativity:
$$x_{it} \in \mathbb{Z}{\geq 0}, \quad y{it} \in {0,1}, \quad s_{it} \geq 0$$
๐๏ธ Concrete Example
We have 3 products over 6 periods.
| Product | $p_i$ (prod cost) | $h_i$ (hold cost) | $f_i$ (setup cost) | $a_i$ (capacity/unit) |
|---|---|---|---|---|
| A | 10 | 2 | 50 | 3 |
| B | 15 | 3 | 80 | 4 |
| C | 12 | 2.5 | 60 | 2 |
Demand $d_{it}$:
| Period | Product A | Product B | Product C |
|---|---|---|---|
| 1 | 20 | 15 | 25 |
| 2 | 30 | 20 | 20 |
| 3 | 25 | 25 | 30 |
| 4 | 20 | 15 | 25 |
| 5 | 35 | 30 | 20 |
| 6 | 25 | 20 | 30 |
Capacity per period: $c_t = 300$ for all $t$
๐ป Python Source Code
1 | # ============================================================ |
๐ Code Walkthrough
Section 1 โ Problem Data
All parameters are defined as plain Python lists and a NumPy array. The demand matrix d has shape (N, T) โ rows are products, columns are periods. M_val is a safe Big-M: the maximum total demand across products multiplied by the horizon, ensuring the setup linkage constraint is never artificially binding.
Section 2 โ Building the MIP Model
We use PuLP, a lightweight LP/MIP modelling library that ships with a free CBC (COIN-OR Branch and Cut) solver.
Three variable families are created:
| Variable | Type | Meaning |
|---|---|---|
x[i][t] |
Integer โฅ 0 | Lot size of product $i$ in period $t$ |
y[i][t] |
Binary | Setup indicator |
s[i][t] |
Continuous โฅ 0 | Ending inventory |
The objective sums production, holding, and setup costs across all $(i, t)$ pairs using pulp.lpSum.
Section 3 โ Constraints
Inventory balance enforces flow conservation. For period 0, there is no previous inventory (initial stock = 0). This is handled cleanly with prev_s = s[i][t-1] if t > 0 else 0.
Setup linkage uses the Big-M technique:
$$x_{it} \leq M \cdot y_{it}$$
This forces $y_{it} = 1$ whenever $x_{it} > 0$, incurring the fixed setup cost.
Capacity limits total machine-hours used each period.
Section 4 โ Solving
PULP_CBC_CMD(msg=0, timeLimit=120) runs CBC silently with a 2-minute time limit. For this small instance, it finds the global optimum in milliseconds.
Section 5โ6 โ Result Extraction & Reporting
Results are extracted from PuLP variable objects via pulp.value(), then converted to NumPy arrays for efficient manipulation. A formatted table is printed for production plan, setup decisions, inventory, and capacity utilization.
๐ Graph Explanations
Plot 1 โ Production Quantities vs Demand
Grouped bars show how much is produced per product per period. Dashed marker lines overlay the actual demand. When a bar exceeds its demand marker, excess is being stored as inventory (intentional batching to amortize setup costs).
Plot 2 โ Ending Inventory Levels
Filled line charts reveal the inventory trajectory. A spike in period $t$ means the optimizer decided to batch-produce ahead of future demand, judging that the setup cost savings outweigh holding costs.
Plot 3 โ Cost Breakdown by Period (Stacked Bar)
Three cost components โ production (blue), holding (amber), setup (red) โ are stacked to show total period cost. Periods with no setup (no red) indicate the product was not produced that period.
Plot 4 โ Capacity Utilization
Bar height = percentage of capacity consumed. Green = comfortable headroom, red = near the limit. This validates that the capacity constraint $\sum_i a_i x_{it} \leq c_t$ is respected in every period.
Plot 5 โ 3D Bar: Production Quantities (Product ร Period)
Each vertical bar represents $x_{it}$. The 3D view makes it immediately clear which product-period combinations receive production runs and how lot sizes vary across the planning horizon.
Plot 6 โ 3D Cost Surface (Product ร Period)
A smooth plasma surface maps $p_i x_{it} + h_i s_{it} + f_i y_{it}$ for every $(i,t)$ cell. Peaks correspond to periods where a setup cost is incurred on top of large production runs. The surface geometry highlights the trade-off structure the solver is navigating.
๐ Execution Results
======================================================= Solver Status : Optimal Total Cost : 6,274.00 ======================================================= โโ Production Plan (x_it) โโ Product P1 P2 P3 P4 P5 P6 Product A 20 30 25 22 33 25 Product B 35 0 40 0 50 0 Product C 45 0 30 45 0 30 โโ Setup Decisions (y_it) โโ Product P1 P2 P3 P4 P5 P6 Product A 1 1 1 1 1 1 Product B 1 0 1 0 1 0 Product C 1 0 1 1 0 1 โโ End Inventory (s_it) โโ Product P1 P2 P3 P4 P5 P6 Product A 0 0 0 2 0 0 Product B 20 0 15 0 20 0 Product C 20 0 0 20 0 0 โโ Capacity Used / Available โโ Period 1: 290 / 300 (96.7% utilization) Period 2: 90 / 300 (30.0% utilization) Period 3: 295 / 300 (98.3% utilization) Period 4: 156 / 300 (52.0% utilization) Period 5: 299 / 300 (99.7% utilization) Period 6: 135 / 300 (45.0% utilization)
[Figure saved as lot_sizing_results.png]
๐ฏ Key Takeaways
Why integer lots matter: Relaxing to continuous variables gives a lower-bound solution that may be infeasible in practice (e.g., 7.3 units of an indivisible component). The MIP guarantees all quantities are whole numbers.
Setup cost vs holding cost trade-off: The optimizer naturally consolidates production into fewer, larger runs when setup costs $f_i$ are high relative to holding costs $h_i$. You can experiment by increasing f and observe how the plan shifts toward longer batches.
Scalability: For this 3-product ร 6-period instance, CBC solves in under a second. Real-world instances with hundreds of products and 52-week horizons may require commercial solvers (Gurobi, CPLEX) or heuristic methods (Lagrangian relaxation, column generation).