Title :

New lower bounds for bin packing problems with conflicts

Author(s) :

Khanafer, Ali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Clautiaux, François [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]

Journal title :

European Journal of Operational Research

Pages :

281-288

Publisher :

Elsevier

Publication date :

2010

ISSN :

0377-2217

English keyword(s) :

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

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL