The Linear Multiple Choice Knapsack Problem.

摘要

We discuss a fast algorithm for the linear programming relaxation of the Multiple Choice Knapsack Problem. Let N be the total number of variables in this problem and let J and J sub 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 sub 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.