.png){kind=icon}
.png){kind=icon}
Return
The min-conflict packing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2011.10.021.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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 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. (C) 2011 Elsevier Ltd. All rights reserved.
Keywords:
Bin packing with conflicts
Knapsack problem
Column generation
Multi-objective optimization
Tabu search
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W