Lower bounds in lot-sizing models: A polyhedral study

Variable lower bounds in Mixed Integer Programs are constraints with the general form x greater than or equal to Ly, where x is a continuous variable and y is a binary or an integer variable. This type of constraints is present in some Lot-Sizing models, where x represents the amount of some article produced by a machine and y is an element of {0, 1} indicates whether the machine is set-up for that article (y = 1) or not (y = 0). In these models, production below some level is not allowed, in order to make full use of resources. In this paper we study, from the polyhedral viewpoint, the mixed integer models whose feasible set includes an additive constraint Sigma x(j) less than or equal to (greater than or equal to, =) D, and constraints Ly(j) less than or equal to x(j) less than or equal to Ky(j), where x(j) are continuous variables, y(j) are integer or binary variables, and K is a large constant. We derive families of strong valid inequalities and show they are sufficient to describe completely the convex hulls of the sets of feasible solutions. Moreover, we develop polynomial algorithms to solve the separation problem associated to each of the families obtained. Finally, we incorporate the inequalities obtained in a cutting plane algorithm, and test their ability to solve some multi-item lot-sizing problems.