Orateur
Description
Lot-Sizing is a class of combinatorial optimization problems encountered in industrial production planning. This work addresses the stochastic capacitated lot-sizing problem with inventory bounds and lost sales. A production problem with uncertain demand is investigated with the assumption that decisions can be regularly updated to adjust to the actual demand being progressively revealed. We focus on a "Decision-Hazard-Decision" information structure derived from industrial applications, in which decisions are made at each stage both before and after uncertainty is revealed. The resulting multi-stage stochastic integer problem is particularly challenging to solve. Namely, the sub-problem to be solved at each decision stage is itself a two-stage stochastic integer program. Highlighting the shortcomings of existing methods to solve this problem, we propose a novel approach based on approximate stochastic dynamic programming. At each stage, the optimal production costs of all future stages depending on the final inventory value of the current stage are represented by a cost-to-go function. From the last stage to the first one, we dynamically construct a piece-wise linear approximation of these cost-to-go functions by solving successive two-stage problems. To further improve the overall solving time, an approximate model is introduced, and a scenario-based decomposition is implemented to efficiently solve each two-stage problem. In particular, a novel polynomial time algorithm for the resulting dual sub-problem is proposed to fasten its solving time. This decomposition method proves to be especially efficient for instances with a large number of uncertainty scenarios at each stage. Numerical results demonstrate that, even if the proposed approach is approximate, it offers practical benefits as it is able to provide production plans of good quality in record time for numerous cases.
Keywords: Lot-sizing, Multi-stage stochastic integer programming, Dynamic programming, Benders decomposition
