Technical Note—The Multiperiod Knapsack Problem

In the multiperiod knapsack problem the decision maker faces a horizon of m periods. Associated with each period are a number of types of items, each with a value and weight. Subject to the requirement that the cumulative capacity of the knapsack in each period i cannot be exceeded by items chosen in periods 1, …, i, the decision maker chooses the most valuable knapsack possible. A branch and bound algorithm exploits the special structure of the multiperiod knapsack problem by calculating bounds by the direct solution of linear programs with m constraints in 0(m) operations. Computational experience is reported on problems ranging in size up to 200 constraints and 1,000 general integer variables.