A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts

摘要

We provide a branch-and-price algorithm for the bin packing problem with conflicts, a variant of the classical bin packing problem that has major applications in scheduling and resource allocation. The proposed algorithm benefits from a number of special features that greatly contribute to its efficiency. First, we use a branching rule that matches the conflicting constraints, preserving the structure of the subproblems after branching. Second, maximal clique valid inequalities are generated based on the conflicting constraints and are added to the subproblems. The algorithm is tested on a standard set of problems and is compared to a recently proposed approach. Numerical results indicate its efficiency and stability.