A Math-Heuristic Dantzig-Wolfe Algorithm for the Capacitated Lot Sizing Problem

摘要

The multi-item multi-period capacitated lot sizing problem with setups (CLST) is a well known optimization problem with wide applicability in real-world production planning problems. Based on a recently proposed Dantzig-Wolfe approach we present a novel math-heuristic algorithm for the CLST. The major contribution of this paper lies in the presentation of an algorithm that exploits exact techniques (Dantzig-Wolfe) in a metaheuristic fashion, in line with the novel trend of math-heuristic algorithms. To the best of the authors knowledge, it is the first time that such technique is employed within a metaheuristic framework, with the aim of tackling challenging instances in short computational time.