A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem

¹ Sorbonne universités, Université de technologie de Compiègne, CNRS, Heudiasyc UMR 7253, CS 60 319, 60 203 Compiègne Cedex, France
² Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar
e-mail: mohamed.haouari@qu.edu.qa

^* e-mail: mehdi.serairi@hds.utc.fr

Received: 24 March 2016
Accepted: 16 March 2017

Abstract

We address the two-dimensional bin packing problem with fixed orientation. This problem requires packing a set of small rectangular items into a minimum number of standard two-dimensional bins. It is a notoriously intractable combinatorial optimization problem and has numerous applications in packing and cutting. The contribution of this paper is twofold. First, we propose a comprehensive theoretical analysis of lower bounds and we elucidate dominance relationships. We show that a previously presented dominance result is incorrect. Second, we present the results of an extensive computational study that was carried out, on a large set of 500 benchmark instances, to assess the empirical performance of the lower bounds. We found that the so-called Carlier-Clautiaux-Moukrim lower bounds exhibits an excellent relative performance and yields the tightest value for all of the benchmark instances.