Discrete Lot-Sizing and Convex Integer Programming.

We study the polyhedral structure of variants of the discrete lot-sizing problem viewed as special cases of convex integer programs. Our approach in studying convex integer programs is to develop results for simple mixed integer sets that can be used to model integer convex objective functions. These results allow us to de ne integral linear programming formulations for the discrete lot-sizing problem in which backlogging and/or safety stocks are present, and to give extended formulations for other cases. Our results help signicantly to solve test cases arising from an industrial application motivating this research.