Skip to Main content Skip to Navigation
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

https://hal.inria.fr/inria-00522668
Contributor : François Clautiaux <>
Submitted on : Friday, October 1, 2010 - 1:35:30 PM
Last modification on : Thursday, April 8, 2021 - 1:53:09 PM

Identifiers

Citation

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

Share

Metrics

Record views

446