Hybrid nested Partitions And Relax-And-Fix approach for capacitated multi-item lot sizing problem

In this paper we consider the capacitated multi-item lot sizing problem with setup times. The problem is to schedule N different items over a horizon of T periods with the objective to minimize the sum of setup cost and inventory holding cost. To achieve feasible high quality solutions, we propose a hybird solution approach which integrates nested partitions and relax-and-fix. Nested partitions is a partitioning and sampling based heuristic method with a global perspective on the problem. Relax-and-fix is implemented to obtain good promising regions and speed up the computational process. Computational results based on benchmark test problems show that the approach is computationally tractable and is able to obtain good results. The approach outperforms other state-of-the-art approaches found in the literature.