INFORMS journal on computing · 2012 · 135 citations · 22 references
Mathematical ProgrammingBranch-and-bound AlgorithmEngineeringDiscrete OptimizationMarket DesignOperations ResearchLogisticsSystems EngineeringDiscrete MathematicsParallel ComputingCombinatorial OptimizationGeneric Branch-and-price AlgorithmMechanism DesignCombinatorial ProblemComputer EngineeringComputer ScienceScheduling ProblemConflict GraphBusinessArbitrary Conflict GraphParallel ProgrammingBranch And BoundInterval Graph
The bin packing problem with conflicts requires packing items into the fewest bins while avoiding placing conflicting items together. The authors employ the BaPCod branch‑and‑price solver, augmenting it with a dynamic‑programming pricing routine for interval‑graph conflicts and a depth‑first‑search branch‑and‑bound pricing strategy for general graphs, and evaluate the method on both literature and synthetically generated instances. The algorithm achieves strong performance, setting new benchmark results by solving all open literature instances within one hour of CPU time.
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.
22