A graph-based heuristic for the non-stationary stochastic lot-sizing problem under penalty costs

We present a relaxation-and-augmentation algorithm to compute near-optimal policy parameters for the single-item single-stocking location non-stationary stochastic lot-sizing problem under penalty costs. Our approach starts from a filtered state-space relaxation of the problem and then systematically repair infeasibilities through a repetitive state-space augmentation procedure, until an optimal solution is obtained. We benchmark our approach against the state-of-the-art MILP-based cut generation approach for the problem; an extensive computational study based on a test bed from the literature demonstrates that our approach is computationally superior on medium and long horizon cases, and hence more scalable.