A Linear Programming Approach for the Three-Dimensional Bin-Packing Problem


In this paper we consider the three-dimensional bin packing problem (3D-BPP), when the bins are identical with the aim of minimizing the number of the used bins. We introduce a mixed-integer linear programming formulation (MILP1). Some special valid inequalities will be presented in order to improve the relaxed lower bound of MILP1. A large set of experimental tests has been carried out. The obtained results show that our method provides a satisfactory performance.

Keywords: Bin-packing; integer linear programming; scheduling.

Mhand Hifi, Imed Kacem, Stephane Negre, Lei Wu


Benchmark instances: download

853total visits.