A Dual Ascent Procedure for Multiproduct Dynamic Demand Coordinated Replenishment with Backlogging
提出一种混合整数规划模型和对偶上升分支定界算法，解决多产品动态需求下的协调补货问题，计算速度比现有最快算法快20倍以上，适用于库存需求规划系统。
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.