A Dual Ascent Procedure for Multiproduct Dynamic Demand Coordinated Replenishment with Backlogging

This paper describes a mixed-integer programming formulation and dual ascent based branch-and-bound algorithm for the multiproduct dynamic demand coordinated replenishment problem with backlogging. The single sourcing properties of the formulation and the hierarchical structure of the fixed-charge and continuous variables yield an extremely tight linear programming relaxation for the problem. A branch-and-bound algorithm based on Erlenkotter's dual ascent, dual adjustment, and primal construction concepts exploits these properties to obtain an efficient solution procedure. Computational results indicate that the new procedures find optimal solutions in less than five percent of the computational time of the most efficient previous algorithm. The heuristic performance of the procedures also demonstrate their superiority over existing approaches. We solved problems with 12 time periods and 20 products in 0.41 CPU seconds, and heuristic solutions with a worst-case three-percent optimality gap are found in 0.068 CPU seconds. The efficiency and large-scale capability of the procedures make their potential application in inventory requirements planning systems promising.