Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm
Ruslan Sadykov, François Vanderbeck
INFORMS Journal on Computing · 2013 · Volume 25 · Issue 2
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.
Keywords
branch and price, bin packing, knapsack, conflict graphs, interval graphs
Enable JavaScript for citation tools and additional paper interactions.