A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph

References

• Akeb H, Hifi M, Ould Ahmed Mounir ME (2011) Local branching-based algorithms for the disjunctively constrained knapsack problem. Comput. Indust. Engrg. 60(4):811–820.Crossref, Google Scholar
• Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375–382.Crossref, Google Scholar
• Dolan ED, More JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J (2011) A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. 23(3):404–415.Link, Google Scholar
• Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2(1):5–30.Crossref, Google Scholar
• Fernandes-Muritiba AE, Iori M, Malaguti E, Toth P (2010) Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3):401–415.Link, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1–3):23–47.Crossref, Google Scholar
• Gendreau M, Laporte G, Semet F (2004) Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31(3):347–358.Crossref, Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Hifi M (2014) An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem. Engrg. Optim. 46(8):1109–1122.Crossref, Google Scholar
• Hifi M, Michrafy M (2006) A reactive local search-based algorithm for the disjunctively constrained knapsack problem. J. Oper. Res. Soc. 57(6):718–726.Crossref, Google Scholar
• Hifi M, Michrafy M (2007) Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34(9):2657–2673.Crossref, Google Scholar
• Hifi M, Otmani N (2012) An algorithm for the disjunctively constrained knapsack problem. Internat. J. Oper. Res. 13(1):22–43.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations, The IBM Research Symposia Series (Springer, New York), 85–103.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Discrete Optim. 8(2):174–190.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems (Wiley, New York).Google Scholar
• Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2):233–249.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Yamada T, Kataoka S, Watanabe K (2002) Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inform. Processing Soc. Japan J. 43(9):2864–2870.Google Scholar