Article ID: | iaor20051543 |
Country: | United Kingdom |
Volume: | 55 |
Issue: | 2 |
Start Page Number: | 187 |
End Page Number: | 197 |
Publication Date: | Feb 2004 |
Journal: | Journal of the Operational Research Society |
Authors: | Lin Edward Y.H., Wu Chung-Min |
Keywords: | heuristics |
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 1 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.