Models and algorithms for three-stage two-dimensional bin packing

Abstract : We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2007, 183 (3), 〈10.1016/j.ejor.2005.11.064〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01224921
Contributeur : Jakob Puchinger <>
Soumis le : jeudi 5 novembre 2015 - 12:06:33
Dernière modification le : dimanche 22 janvier 2017 - 12:13:48
Document(s) archivé(s) le : samedi 6 février 2016 - 11:19:19

Fichier

puchinger-05b.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jakob Puchinger, Günther Raidl. Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, Elsevier, 2007, 183 (3), 〈10.1016/j.ejor.2005.11.064〉. 〈hal-01224921〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

149