The multiple-choice multi-period knapsack problem

作     者：Lin, EY Wu, CM 

作者机构：Natl Taipei Univ Technol Coll Management Dept Business Management Taipei 106 Taiwan 

出 版 物：《JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY》 (英国运筹学会志)

年 卷 期：2004年第55卷第2期

页      面：187-197页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主　　题：knapsack problem non-convex programming integer programming multiple-choice programming 

摘      要：This paper introduces the multiple-choice multi-period knapsack problem in the interface of multiple-choice programming and knapsack problems. We first examine the properties of the multiple-choice multi-period knapsack problem. A heuristic approach incorporating both primal and dual gradient methods is then developed to obtain a strong lower bound. Two branch-and-bound procedures for special-ordered-sets type I variables that incorporate, respectively, a special algorithm and the multiple-choice programming technique are developed to locate the optimal solution using the above lower bound as the initial solution. A computer program written in IBM s APL2 is developed to assess the quality of this lower bound and to evaluate the performance of these two branch-and-bound procedures.