Abstract (David Pisinger)

The Multiple Loading Problem (also called Multiple Knapsack Problem) is the problem of choosing some of n items to be loaded in m distinct containers, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the containers. The problem has several applications in naval as well as financial management, but due to the NP-hardness, current algorithms cannot solve instances of large size.

A new exact algorithm for the Multiple Knapsack Problem is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm use Surrogate relaxation for deriving upper bounds, and lower bounds are obtained by splitting the surrogate solution into the m knapsacks by solving a series of Subset-sum Problems. A new separable dynamic programming algorithm is presented for the solution of Subset-sum Problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds.

The developed algorithm is compared to the MTM algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is, that several large instances with n=100000 items may be solved in a fraction of a second.


Last modified: December 5, 1995.
Kim Skak Larsen (kslarsen@imada.sdu.dk)