The multiple-choice multi-period knapsack problem

The multiple-choice multi-period knapsack problem

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.