Skip to Main content Skip to Navigation
Journal articles

Tree decomposition based heuristics for the two-dimensional bin packing problem with conflicts

Ali Khanafer 1 François Clautiaux 1 El-Ghazali Talbi 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00750717
Contributor : Talbi El-Ghazali <>
Submitted on : Monday, November 12, 2012 - 10:37:37 AM
Last modification on : Friday, April 23, 2021 - 9:57:48 AM

Identifiers

Citation

Ali Khanafer, François Clautiaux, El-Ghazali Talbi. Tree decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Computers and Operations Research, Elsevier, 2012, 39 (1), pp.54-63. ⟨10.1016/j.cor.2010.07.009⟩. ⟨hal-00750717⟩

Share

Metrics

Record views

426