Skip to Main content Skip to Navigation
New interface
Journal articles

New lower bounds for bin packing problems 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 : The bin packing problem with conflicts (BPC) consists of minimizing the number of bins used to pack a set of items, where some items cannot be packed together in the same bin due to compatibility restrictions. The concepts of dual-feasible functions (DFF) and data-dependent dual-feasible functions (DDFF) have been used in the literature to improve the resolution of several cutting and packing problems. In this paper, we propose a general framework for deriving new DDFF as well as a new concept of generalized data-dependent dual-feasible functions (GDDFF), a conflict generalization of DDFF. The GDDFF take into account the structure of the conflict graph using the techniques of graph triangulation and tree-decomposition. Then we show how these techniques can be used in order to improve the existing lower bounds.
Document type :
Journal articles
Complete list of metadata
Contributor : François Clautiaux Connect in order to contact the contributor
Submitted on : Friday, October 1, 2010 - 1:35:30 PM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM



Ali Khanafer, François Clautiaux, El-Ghazali Talbi. New lower bounds for bin packing problems with conflicts. European Journal of Operational Research, 2010, 2 (206), pp.281-288. ⟨10.1016/j.ejor.2010.01.037⟩. ⟨inria-00522668⟩



Record views