The Linear Multiple Choice Knapsack Problem

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.