Lower bounds and algorithms for the minimum cardinality bin covering problem

This paper introduces the minimum cardinality bin covering problem where we are given m identical bins with capacity C and n indivisible items with integer weights wj(j=1,…,n). The objective is to minimize the number of items packed into the m bins so that the total weight of each bin is at least equal to C. We discuss reduction criteria, derive several lower bound arguments and propose construction heuristics as well as a powerful subset sum-based improvement algorithm that is even optimal when m=2. Moreover, we present a tailored branch-and-bound method which is able to solve instances with up to 20 bins and several hundreds of items within a reasonable amount of time. In a comprehensive computational study on a wide range of randomly generated instances, our algorithmic approach proved to be much more effective than a commercial solver.