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

References

• Baker BS, Coffman EG. Mutual exclusion scheduling. Theoret. Comp. Sci. (1996) 162(2):225–243Crossref, Google Scholar
• Beaumont O, Bonichon N, Duchon P, Larchevêque H, Shuartsman AA, Felber P. Distributed approximation algorithm for resource clustering. Structural Information and Communication Complexity (2008) 5058(Springer, Heidelberg, Germany) 61–73Lecture Notes in Computer ScienceCrossref, Google Scholar
• Busygin S. A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. (2006) 154(15):2080–2096Crossref, Google Scholar
• Carraghan R, Pardalos PM. An exact algorithm for the maximum clique problem. Oper. Res. Lett. (1990) 9(6):375–382Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P, Christofides N, Mingozzi A, Toth P, Sandi C. The vehicle routing problem. Combinatorial Optimization (1979) (Wiley, Chichester, UK) 315–338Google Scholar
• Corneil DG, Olariu S, Stewart L, Karloff HJ. The ultimate interval graph recognition algorithm? SODA '98: Proc. Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (1998) (Society for Industrial and Applied Mathematics, Philadelphia) 175–180Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J. A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. (2011) 23(3):404–415Link, Google Scholar
• Falkenauer E. A hybrid grouping genetic algorithm for bin packing. J. Heuristics (1996) 2(1):5–30Crossref, Google Scholar
• Fernandes Muritiba AE, Iori M, Malaguti E, Toth P. Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. (2010) 22(3):401–415Link, Google Scholar
• Gardi F. Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apparentée: complexité et algorithmes. (2005) . Ph.D. thesis, Université de la Méditerranée-Aix-Marseille II, Marseille, FranceGoogle Scholar
• Gardi F. Mutual exclusion scheduling with interval graphs or related classes. Discrete Appl. Math. (2009) 157(1):19–35Part iCrossref, Google Scholar
• Gendreau M, Laporte G, Semet F. Heuristics and lower bounds for the bin packing problem with conflicts. Comp. Oper. Res. (2004) 31:347–358Crossref, Google Scholar
• Harvey WD, Ginsberg ML, Mellish CS. Limited discrepancy search. IJCAI'95: Proc. 14th Internat. Joint Conf. Artificial Intelligence (1995) (Morgan Kaufmann, San Francisco) 607–613Google Scholar
• Hifi M, Michrafy M. Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comp. Oper. Res. (2007) 34(9):2657–2673Crossref, Google Scholar
• Jansen K. An approximation scheme for bin packing with conflicts. J. Combin. Optim. (1999) 3(4):363–377Crossref, Google Scholar
• Jansen K, Öhring S. Approximation algorithms for time constrained scheduling. Inform. Comp. (1997) 132(2):85–108Crossref, Google Scholar
• Johnson EL, Padberg MW. A note on the knapsack problem with special ordered sets. Oper. Res. Lett. (1981) 1(1):18–22Crossref, Google Scholar
• Joncour C, Michel S, Sadykov R, Sverdlov D, Vanderbeck F. Column generation based primal heuristics. Electronic Notes in Discrete Math. (2010) 36:695–702Crossref, Google Scholar
• Kelleler H, Pferschy U, Pisinger D. Knapsack Problems (2004) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Laporte G, Desroches S. Examination timetabling by computer. Comp. Oper. Res. (1984) 11(4):351–360Crossref, Google Scholar
• Martello S, Toth P. Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, New York) Google Scholar
• Pferschy U, Schauer J. The knapsack problem with conflict graphs. J. Graph Algorithms Appl. (2009) 13(2):233–249Crossref, Google Scholar
• Ryan DM, Foster BA, Wren A. An integer programming approach to scheduling. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (1981) (North-Holland, Amsterdam) 269–280Google Scholar
• Vanderbeck F. Branching in branch-and-price: A generic scheme. Math. Programming (2011) 130(2):249–294Crossref, Google Scholar
• Vanderbeck F, Savelsbergh MWP. A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper. Res. Lett. (2006) 34(3):296–306Crossref, Google Scholar
• Vanderbeck F, Wolsey LA, Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA. Reformulation and decomposition of integer programs. 50 Years of Integer Programming 1958–2008 (2010) (Springer, Heidelberg, Germany) 431–502Crossref, Google Scholar