adventures in optimization

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.

$\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$.