We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm.
- Authors
Sadykov, Ruslan; Vanderbeck, François
- Abstract
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.
- Subjects
BIN packing problem; HEURISTIC algorithms; GENERIC programming (Computer science); COMPUTER programming; LITERATURE reviews; CENTRAL processing units
- Publication
INFORMS Journal on Computing, 2013, Vol 25, Issue 2, p244
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.1120.0499