The Linear Multiple Choice Knapsack Problem

Abstract

A fast algorithm is presented for the linear programming relaxation of the Multiple Choice Knapsack Problem. If N is the total number of variables and J and J max denote the total number of multiple choice variables and the cardinality of the largest multiple choice set, respectively, the running time of the algorithm is then bounded by 0(J log J max ) + 0(N). Under certain conditions it is possible to reduce this bound to 0(N) steps on the average. Possible further improvements are also discussed.