The charming adventures of an analyst and his solver.
Formulation and aspects of the Uncapacitated Lot Sizing problem in Integer Programming.
Uncapacitated Lot Sizing (ULS) is a classic OR problem that seeks to minimize the cost of satisfying known demand for a product over time. Demand is subject to varying costs for production, set-up, and storage of the product. Technically, it is a mixed binary integer linear program -- the key point separating it from the world of linear optimization being that production cannot occur during any period without paying that period's fixed costs for set-up. Thus it has linear nonnegative variables for production and storage amounts during each period, and a binary variable for each period that determines whether or not production can actually occur.
For $n$ periods with per-period fixed set-up cost $f_t$, unit production cost $p_t$, unit storage cost $h_t$,and demand $d_t$, we define decision variables related to production and storage quantities:
One can minimize overall cost for satisfying all demand on time using the following model per Wolsey (1998), defined slightly differently here:
| $\min$ | $z = \sum_t{p_t x_t} + \sum_t{h_t s_t} + \sum_t{f_t y_t}$ | |||
| s.t. | $s_1$ | $=$ | $d_1 + s_1$ | |
| $s_{t-1} + x_t$ | $=$ | $d_t + s_t$ | $\forall t > 1$ | |
| $x_t$ | $\leq$ | $M y_t$ | $\forall t$ | |
| $s_t, x_t$ | $\geq$ | $0$ | $\forall t$ | |
| $y_t$ | $\in$ | $\{0,1\}$ | $\forall t$ | |
According to Wolsey, page 11, given that $s_t = \sum_{i=1}^t (x_i - d_i)$ and defining new constants $K = \sum_{t=1}^n h_t(\sum_{i=1}^t d_i)$ and $c_t = p_t + \sum_{i=t}^n h_i$, the objective function can be rewritten as $z = \sum_t c_t x_t + \sum _t f_t y_t - K$. The book lacks a proof of this and it seems a bit non-obvious, so I attempt an explanation in somewhat painstaking detail here.
| Proof: | ||
| $\sum_t p_t x_t + \sum_t h_t s_t + \sum_t f_t y_t$ | $=$ | $\sum_t c_t x_t + \sum _t f_t y_t - K$ |
| 1. Eliminate $\sum_t f_t y_t$: | ||
| $\sum_t p_t x_t + \sum_t h_t s_t$ | $=$ | $\sum_t c_t x_t - K$ |
| 2. Expand $K$ and $c_t$: | ||
| $\sum_t p_t x_t + \sum_t h_t s_t$ | $=$ | $\sum_t (p_t + \sum_{i=t}^n h_i) x_t - \sum_t h_t (\sum_{i=1}^t d_i)$ |
| 3. Eliminate $\sum_t p_t x_t$: | ||
| $\sum_t h_t s_t$ | $=$ | $\sum_t x_t (\sum_{i=t}^n h_i) - \sum_t h_t (\sum_{i=1}^t d_i)$ |
| 4. Expand $s_t$: | ||
| $\sum_t h_t (\sum_{i=1}^t x_i) - \sum_t h_t (\sum_{i=1}^t d_i)$ | $=$ | $\sum_t x_t (\sum_{i=t}^n h_i) - \sum_t h_t (\sum_{i=1}^t d_i)$ |
| 5. Eliminate $\sum_t h_t (\sum_{i=1}^t d_i)$: | ||
| $\sum_t h_t (\sum_{i=1}^t x_i)$ | $=$ | $\sum_t x_t (\sum_{i=t}^n h_i)$ |
The result from step 5 becomes obvious upon expanding its left and right-hand terms:
In matrix notation with $h$ and $x$ as column vectors in $\bf R^n$ and $L$ and $U$ being $n x n$ lower and upper triangular identity matrices, respectively, this can be written as:
or $h^T L x = x^T U h$.