Heuristics Algorithms Based on a Linear Programming for the Three-Dimensional Bin-Packing Problem

In this paper we consider the three-dimensional bin packing problem (3D-SBSBPP) under the assumption that all the bins are of a single size. Such a problem is a well-known NP-hard problem and consists in packing a set of items in a minimal number of bins. First, we introduce a mixed-integer linear model to formulate the problem (MILP1). Some special valid inequalities are used in order to improve the relaxed lower bound (LB) of MILP1. Then, we introduce some new heuristics to compute upper bounds by solving a sequence of single bin filling problems. Finally, we present our exprimental results to evaluate the proposed algorithms.