We study the dual version of the minimum cardinality bin packing problem.

We develop strong lower bounds and analyze their worst-case performances.

We suggest constructive heuristics and a subset sum-based improvement heuristic.

We propose a branch-and-bound algorithm to determine an optimal solution.

Our algorithms proved to be effective on a wide range of randomly generated instances.