We introduce and investigate the Bin Packing Problem with Setups (BPPS), a generalization of the bin packing problem in which the items are partitioned into classes, each having a setup weight and a setup cost. We first investigate a natural formulation of the problem with a variable for each pair of item and bin, and show how its linear programming relaxation can be solved in closed-form in linear time and establish an asymptotic bound on its optimality gap. We then propose an approximation scheme for combining approximation algorithms for the classical bin packing problem so to obtain solutions to the BPPS within a constant approximation factor. We then propose a formulation with exponentially-many columns suitable for column generation methods, and propose a branch-and-cut-and-price algorithm based on it. The method relies on a two-level branching scheme and on the separation of subset row inequalities, and it is also enhanced via a preprocessing procedure and a bound-tightening one. Extensive computational experiments show the effectiveness of our approach when compared to off-the-shelf methods.
This is joint work with Fabio Furini.