DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                         The Multiple Loading Problem                        

                                David Pisinger                               
                        Department of Computer Science                       
                           University of Copenhagen                          

                    Tuesday, February 6, 1996, at 2:15 PM                    
                               The Seminar Room                              


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.


                                                         Joergen Bang-Jensen