Branch-and-Price for the Set-Union Bin Packing Problem

Given a set of items, each requiring a set of elements, the set-union bin packing problem (SUBP) consists of grouping all items into a minimum number of bins such that each item is assigned to exactly one bin and the total weight of all distinct elements required in a bin does not exceed its capacity. The SUBP is a generalization of the well-known bin-packing problem, where items can share one or more elements in a nonadditive fashion. In the literature, it has been addressed by various names such as pagination problem, job grouping problem, tool switching problem, or bin packing problem with overlapping items. We propose a branch-and-price (B&P) algorithm for solving the SUBP. For the column-generation pricing problem, which is a set-union knapsack problem (SUKP), we present and explore alternative solution methods, namely the direct solution of an integer program with a general-purpose MIP solver and two labeling algorithms on ad hoc defined graphs. The overall best B&P variant combines an upfront greedy pricing heuristic and an item-based labeling approach without the application of any dominance. The latter is based on the representation of the pricing problem as a shortest path problem with resource constraints and relies on strong completion bounds as acceleration technique. Ryan-and-Foster branching is applied to ensure integer solutions. Extensive computational results demonstrate the effectiveness of the proposed method. Our B&P significantly outperforms the state-of-the-art IP formulations. It solves to optimality more than 10,000 instances from the literature that have only been solved heuristically before, improving the best known solutions for more than half of the benchmark.