An Algorithm for the Penalized Multiple Choice Knapsack Problem

We present an algorithm for the penalized multiple choice knapsack problem (PMCKP), a combination of the more common penalized knapsack problem (PKP) and multiple choice knapsack problem (MCKP). Our approach is to converts a PMCKP into a PKP using a previously known transformation between MCKP and KP, and then solve the PKP greedily. For PMCKPs with well-behaved penalty functions, our algorithm is optimal for the linear relaxation of the problem.

Authors

• Elizabeth Hilliard
• Amy Greenwald
• Victor Naroditskiy

Keywords

No keywords are indexed for this paper.