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

Abstract

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

doi:10.1016/j.endm.2010.05.126

Benchmark instances: download

1104total visits.