The charming adventures of an analyst and his solver.

Friday, February 20, 2009
»

*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:

$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:

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