An exact algorithm for large multiple knapsack problems

The MULKNAP algorithm, which is based on the MTM framework of Martello and Toth, is the first algorithm capable of solving large sized cases up to n=100,000 with data range of as much as R=10,000. MULKNAP uses specialized algorithms to derive both lower bounds and upper bounds as well as solve the Subset-sum Problem. It has been demonstrated that despite the unsuitability of Multiple Knapsack Problem in dynamic programming, dynamic programming algorithms can be used to provide the needed solutions.