The charming adventures of an analyst and his solver.

Friday, February 20, 2009 »

## Uncapacitated Lot Sizing Formulation

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:

$x_t =$ units produced in period $t$
$s_t =$ stock at the end of period $t$
$y_t = 1$ if production occurs in period $t$, $0$ otherwise

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:

$h_1 x_1 + h_2 (x_1 + x_2) + \cdots + h_n (x_1 + \cdots + x_n) =$ $x_1 (h_1 + \cdots + h_n) + x2 (h_2 + \cdots + h_n) + \cdots + x_n h_n$.

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:

$\left(h_1 \cdots h_n\right)\left(\matrix{1 \cdots 0 \cr \vdots\ddots \vdots \cr 1 \cdots 1}\right)\left(\matrix{x_1 \cr \vdots \cr x_n}\right) = \left(x_1 \cdots x_n \right)\left(\matrix{1 \cdots 1 \cr \vdots \ddots \vdots \cr 0 \cdots 1}\right)\left(\matrix{h_1 \cr \vdots \cr h_n}\right)$

or $h^T L x = x^T U h$.