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

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 54-63

Ali, Khanafer , François, Clautiaux , El-Ghazali, Talbi

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…