Journal of Northeastern University ›› 2003, Vol. 24 ›› Issue (1): 11-14.DOI: -

• OriginalPaper • Previous Articles     Next Articles

Branch-and-Price algorithm for CLSP

Gao, Zhen (1); Tang, Li-Xin (1)   

  1. (1) Sch. of Info. Sci. and Eng., Northeastern Univ., Shenyang 110004, China
  • Received:2013-06-23 Revised:2013-06-23 Online:2003-01-15 Published:2013-06-23
  • Contact: Gao, Z.
  • About author:-
  • Supported by:
    -

Abstract: 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.

CLC Number: