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

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

0.00 Avg rating0 Votes
Article ID: iaor20117845
Volume: 23
Issue: 3
Start Page Number: 404
End Page Number: 415
Publication Date: Jun 2011
Journal: INFORMS Journal on Computing
Authors: , , ,
Keywords: heuristics
Abstract:

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.

Reviews

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