Improved Sets of Points for the Bin Packing Problem

The bin packing problem has a large number of applications. Some of its solution methods are based on the positioning of items, as arc-flow formulations. Approaches for reducing the number of positions at which items can be arranged have been proposed since the seventies until very recently with the sets of meet-in-the-middle patterns. In this paper, we propose a new approach, based on an arbitrary ordering of items, that results in an improved set of points. The idea consists of eliminating redundant positions by right- and left-aligning items in solutions. The computational experiments carried out on benchmark instances have shown that the proposed sets outperformed the regular normal patterns in 70.8% and the meet-in-the-middle in 43.4%, on average. This opens new possibilities of future research, not only in terms of formulations for the bin packing problem but also in terms of generalization for problems of higher dimensions.