The min-conflict packing problem
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
The min-conflict packing problem
Auteur(s) :
Khanafer, Ali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Clautiaux, François [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Hanafi, Said [Auteur]
Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 [LAMIH]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Clautiaux, François [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Hanafi, Said [Auteur]
Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 [LAMIH]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Titre de la revue :
Computers and Operations Research
Pagination :
2122-2132
Éditeur :
Elsevier
Date de publication :
2011-10-29
ISSN :
0305-0548
Discipline(s) HAL :
Computer Science [cs]/Operations Research [math.OC]
Résumé en anglais : [en]
In the classical bin-packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the ...
Lire la suite >In the classical bin-packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the min-conflict packing problem (MCBP), in which we minimize the number of violated conflicts when the number of bins is fixed. In order to find a tradeoff between the number of bins used and the violation of the conflict constraints, we also consider a bi-objective version of this problem. We show that the special structure of its Pareto front allows to reformulate the problem as a small set of MCBP. We solved these two problems through heuristics, column-generation methods, and a tabu search. Computational experiments are reported to assess the quality of our methods.Lire moins >
Lire la suite >In the classical bin-packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the min-conflict packing problem (MCBP), in which we minimize the number of violated conflicts when the number of bins is fixed. In order to find a tradeoff between the number of bins used and the violation of the conflict constraints, we also consider a bi-objective version of this problem. We show that the special structure of its Pareto front allows to reformulate the problem as a small set of MCBP. We solved these two problems through heuristics, column-generation methods, and a tabu search. Computational experiments are reported to assess the quality of our methods.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- fulltext.pdf
- Accès libre
- Accéder au document