New lower bounds for bin packing problems with conflicts |
| |
Authors: | Ali Khanafer,Franç ois Clautiaux,El-Ghazali Talbi |
| |
Affiliation: | Université des Sciences et Technologies de Lille, LIFL CNRS UMR 8022, INRIA Lille - Nord Europe Bâtiment INRIA, Parc de la Haute Borne, 59655 Villeneuve d’Ascq, France |
| |
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. |
| |
Keywords: | Bin packing with conflicts Knapsack problem Lower bounds Chordal graphs Tree-decomposition Dual-feasible functions |
本文献已被 ScienceDirect 等数据库收录! |
|