Abstract | ||
---|---|---|
We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it generalizes both the bin packing problem and the vertex coloring problem. We present new lower bounds, upper bounds, and an exact approach, based on a set covering formulation solved through a branch-and-price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1287/ijoc.1090.0355 | INFORMS Journal on Computing |
Keywords | Field | DocType |
benchmark instance,branch-and-price algorithm,extensive computational result,bin packing problem,particular bin packing problem,real-world application,proposed procedure,new lower bound,exact approach,vertex coloring problem,heuristics,branch and price | Discrete mathematics,Mathematical optimization,Bin,Vertex (geometry),Best bin first,Branch and price,Algorithm,Heuristics,Cutting stock problem,Set packing,Bin packing problem,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 3 | 1091-9856 |
Citations | PageRank | References |
21 | 0.95 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Albert E. Fernandes Muritiba | 1 | 21 | 0.95 |
Manuel Iori | 2 | 790 | 46.05 |
Enrico Malaguti | 3 | 312 | 21.69 |
Paolo Toth | 4 | 326 | 20.42 |