Branch-and-Price algorithm for CLSP

作者：Gao Zhen^*; Tang Li Xin

来源：Journal of Northeastern University, 2003, 24(1): 11-14.

• Branch and bound
• Column generation
• Production plan
• The capacitated single level multi item dynamic lot sizing problem

A Branch-and-Price approach was presented to solve the classical capacitated single-level multi-item dynamic lot-sizing problems, also called as CLSP. Its objective is to minimize the sum of set-up and inventory-holding costs over the horizon under consideration, such as demands, capacity restrictions, etc. CLSP is frequently encountered in the most industry settings and well known as NP-Hard problem. The Branch-and-Price approach, a generalization of branch-and-bound with LP relaxation, allows column generation to be applied throughout explored nodes in the branch-and-bound tree. An implementation of the branch-and-price approach was described in detail. Two groups of examples were computed to verify the correctness and advantages of the suggested approach.

• 出版日期2003
• 单位东北大学