On the capacitated lot-sizing and continuous 01 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 01 knapsack problem, which has been introduced recently and has been shown to provide a useful relaxation of mixed 01 integer programs. We then show that by studying an appropriate continuous 01 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.
capacitated lot-sizing continuous 01 knapsack problem integer programming