On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra

We consider the single item capacitated lot-sizing problem, a well-known production planning model that often arises in practical applications, and derive new classes of valid inequalities for it. We first derive new, easily computable valid inequalities for the continuous 0-1 knapsack problem, which has been introduced recently and has been shown to provide a useful relaxation of mixed 0-1 integer programs. We then show that by studying an appropriate continuous 0-1 knapsack relaxation of the capacitated lot-sizing problem, it is possible not only to derive new classes of valid inequalities for the capacitated lot-sizing problem, but also to derive and/or strengthen several known classes. (C) 2000 Elsevier Science B.V. All rights reserved.