New lower bounds for bin packing problems with conflicts

作者：Khanafer Ali; Clautiaux Francois^*; Talbi El Ghazali

来源：European Journal of Operational Research, 2010, 206(2): 281-288.

DOI：10.1016/j.ejor.2010.01.037

• Bin packing with conflicts
• Knapsack problem
• Lower bounds
• Chordal graphs
• Tree-decomposition
• Dual-feasible functions

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 DOFF. 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.

• 出版日期2010-10-16
• 单位INRIA