Lagrangian heuristic for Capacitated Lot Sizing Problems

In the field of operations research, the the Lot Sizing Problem (LSP) aims to satisfy the demand of clients while minimizing setup and inventory holding costs. The aim of this dissertation is to propose efficient tools and investigate optimization methods to solve different variants of LSP. The thesis is organized in two parts: in the first one we focus on deterministic problem while in the second one we focus on the stochastic version of the problem. In particular, in the first part, we propose a Lagrangian relaxation approach to solve the deterministic Capacitated LSP (CLSP) on multiple items, with both set up costs and set up times. If at least two items are considered the CLSP is NP-Hard and the exact implementation of the model need MILP to be solved. Lagrange multipliers allow us to eliminate the capacity constraint and to solve the uncapacitated problem for each product. To perform this step we propose two different algorithm, the first based on the Wagner Whitin method, the second based on a Cross Entropy approach. Lagrange multipliers are updated by subgradient method with variable step sizes. Several approaches to speed up the convergence of the method and build a feasible solution are proposed. In order to prove the effectiveness of the proposed approach we test our results against the one provided by exact solver. The analyses made, allowed us to claim that, in most of the cases tested, especially as the number of products increases, our algorithm is able to perform better than the exact MILP resolution. In particular, it is investigated how the ratio between set up costs and holding costs influence the results. In the second part, we deal with the uncapacitated LSP on the single item under demand uncertainty and lost sales assumption. Although it is assumed that the distribution of demand is known and there is therefore no distributional ambiguity, in case the demand is continuously distributed, some kind of approximation must be made. Instead of using the classic model with recourse, we approach the problem using Dynamic Programming (DP) methods and Reinforcement Learning (RL). Given the sometimes prohibitive size of the problem, an approximate DP algorithm is implemented and the value function is approximated through the use of cubic splines. Also in the case of the RL-based algorithm, approximations are needed to avoid the curse of dimensionality. We use a Q Learning approach with finite state space and finite time horizon, and estimate the Q-factors by means of linear regression. Both proposed algorithms are compared with the well-known (s,S) policy, valid only under the assumption of stationary demand (situation in which this policy is used as a benchmark). In cases where this supposition falls, it is however implemented to assess the performance of the proposed algorithms. Finally, the problem is studied in the capacitated case, where a procedure based on Lagrange multipliers, similar to that built in the deterministic case, is implemented. Heuristics for the approximation of the value function are proposed to speed up the execution of the algorithm.