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.