  The Submodular Bin Packing (SMBP) problem asks for packing unsplittable items
into a minimal number of bins for which the capacity utilization function is
submodular. SMBP is equivalent to chance-constrained and robust bin packing
problems under various conditions. SMBP is a hard binary nonlinear programming
optimization problem. In this paper, we propose a branch-and-price algorithm to
solve this problem. The resulting price subproblems are submodular knapsack
problems, and we propose a tailored exact branch-and-cut algorithm based on a
piece-wise linear relaxation to solve them. To speed up column generation, we
develop a hybrid pricing strategy to replace the exact pricing algorithm with a
fast pricing heuristic. We test our algorithms on instances generated as
suggested in the literature. The computational results show the efficiency of
our branch-and-price algorithm and the proposed pricing techniques.
