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.