The Bin Packing Problem with Setups: Formulations, Structural Properties and Computational Insights

Abstract

We introduce the Bin Packing Problem with Setups (BPPS), a generalization of the classical Bin Packing Problem with applications in production planning and logistics. In this problem, the items are partitioned into classes, and packing items of a class in a bin incurs a setup weight and cost. We propose a natural Integer Linear Programming (ILP) formulation for the BPPS and analyze its Linear Programming relaxation. We show that the resulting lower bound can be arbitrarily weak and introduce the Minimum Classes Inequalities (MCIs), which guarantee a worst-case ratio of 1/2 with respect to the optimal objective function value of the BPPS. We also derive the Minimum Bins Inequality (MBI) and an upper bound on the number of bins in any optimal solution, substantially reducing the formulation size. We further develop an arc-flow formulation for the BPPS based on a tailored graph construction and compression procedure. Its LP relaxation dominates that of the natural formulation, and both the MCIs and the MBI are extended to the arc-flow model. Finally, we introduce a benchmark comprising 576 randomly generated instances and 36 real-world instances derived from a vehicle-routing application, and conduct extensive computational experiments. Results show that the natural formulation performs best on instances with small or medium item weights, whereas the arc-flow formulation is more effective for large item weights and on the real-world testbed.