id: 06060529
dt: j
an: 06060529
au: Elhedhli, Samir; Li, Lingzi; Gzara, Mariem; Naoum-Sawaya, Joe
ti: A branch-and-price algorithm for the bin packing problem with conflicts.
so: INFORMS J. Comput. 23, No. 3, 404-415 (2011).
py: 2011
pu: INFORMS, Hanover, MD
la: EN
cc: 
ut: bin packing problem with conflicts; branch and price; Lagrangean
    relaxation; maximal clique inequalities
ci: 
li: doi:10.1287/ijoc.1100.0406
ab: Summary: 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.
rv: