Journal
INFORMS JOURNAL ON COMPUTING
Volume 25, Issue 2, Pages 244-255Publisher
INFORMS
DOI: 10.1287/ijoc.1120.0499
Keywords
branch and price; bin packing; knapsack; conflict graphs; interval graphs
Ask authors/readers for more resources
The bin packing problem with conflicts consists of packing items in a minimum number of bins of limited capacity while avoiding joint assignments of items that are in conflict. Our study demonstrates that a generic implementation of a branch-and-price algorithm using specific pricing oracle yields comparatively good performance for this problem. We use our black-box branch-and-price solver BaPCod, relying on its generic branching scheme and primal heuristics. We developed a dynamic programming algorithm for pricing when the conflict graph is an interval graph, and a depth-first-search branch-and-bound approach for pricing when the conflict graph has no special structure. The exact method is tested on instances from the literature where the conflict graph is an interval graph, as well as harder instances that we generated with an arbitrary conflict graph and larger number of items per bin. Our computational experiment report sets new benchmark results for this problem, closing all open instances of the literature in one hour of CPU time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available