Smaller compact formulation for lot-sizing with constant batches
Please always quote using this URN: urn:nbn:de:0297-zib-11956
- We consider a variant of the classical lot-sizing problem in which the capacity in each period is an integer multiple of some basic batch size. Pochet and Wolsey (Math. Oper. Res. 18, 1993) presented an O(n^2 min{n,C}) algorithm to solve this problem and a linear program with O(n^3) variables and inequalities, where n is the number of periods and C the batch size. We provide a linear program of size O(n^2 min{n,C}), that is, in case that C < n, our formulation is smaller.
| Author: | Rüdiger Stephan |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | compact formulation; constant batch size; lot-sizing |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| Date of first Publication: | 2010/12/31 |
| Series (Serial Number): | ZIB-Report (10-30) |
| ZIB-Reportnumber: | 10-30 |
