A study of the lot-sizing polytope (Q1881043): Difference between revisions

This is an analysis of the convex hull of feasible solutions \(F\) of the lot-sizing problem in bottleneck flow formulation. First, it is shown that the convex hull of \(F\) is full dimensional and trivial facets are given. Then the authors define bottlenecks of sets \(S\) and bottleneck covers to introduce bottleneck cover inequalities (BCI). These inequalities are at least as strong as flow cover inequalities and surrogate flow cover inequalities. It is shown that they are valid and that every fractional extreme point of the linear relaxation is defined by a bottleneck cover: BCI cut off all fractional extreme points. Necessary and sufficient conditions for BCI to be facet defining for conv(\(F\)) are given. Furthermore, lifted bottleneck covers are investigated. It is shown that these inequalities yield a complete description of conv(\(F\)) for the uncpacitated case and a polynomial time separation algorithm is given for the constant capacity case. Finally, numerical experiments show that the cuts are effective in solving lot-sizing problems.