Bin Packing with Conflicts: A Generic Branch‐and‐Price Algorithm

Bin Packing with Conflicts: A Generic Branch‐and‐Price Algorithm

0.00 Avg rating0 Votes
Article ID: iaor20132449
Volume: 25
Issue: 2
Start Page Number: 244
End Page Number: 255
Publication Date: Mar 2013
Journal: INFORMS Journal on Computing
Authors: ,
Keywords: bin packing, branch and price
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.

Reviews

Required fields are marked *. Your email address will not be published.