A Branch-and-Price Algorithm for the Multiple Knapsack Problem

References

• Alves C, Valério de Carvalho JM (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput. Oper. Res. 35:1315–1328.Crossref, Google Scholar
• Belov G, Scheithauer G (2002) A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res. 141(2):274–294.Crossref, Google Scholar
• Côté JF, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J. Comput. 30(4):646–661.Link, Google Scholar
• Dell’Amico M, Delorme M, Iori M, Martello S (2019) Mathematical models and decomposition methods for the multiple knapsack problem. Eur. J. Oper. Res. 274(3):886–899.Crossref, Google Scholar
• Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32(1):101–119.Link, Google Scholar
• Detti P (2009) A polynomial algorithm for the multiple knapsack problem with divisible item sizes. Inform. Processing Lett. 109(11):582–584.Crossref, Google Scholar
• Detti P (2021) A new upper bound for the multiple knapsack problem. Comput. Oper. Res. 129:105210.Crossref, Google Scholar
• Fukunaga AS (2011) A branch-and-bound algorithm for hard multiple knapsack problems. Ann. Oper. Res. 184:97–119.Crossref, Google Scholar
• Fukunaga AS, Korf RE (2005) Bin-completion algorithms for multicontainer packing and covering problems. J. Artificial Intelligence Res. 28:393–429.Crossref, Google Scholar
• Görtz S, Klose A (2012) A simple but usually fast branch-and-bound algorithm for the capacitated facility location problem. INFORMS J. Comput. 24(4):597–610.Link, Google Scholar
• Hung MS, Fisk JC (1978) An algorithm for 0-1 multiple-knapsack problems. Naval Res. Logist. Quart. 25(3):571–579.Crossref, Google Scholar
• Hung MS, Fisk JC (1979) A heuristic routine for solving large loading problems. Naval Res. Logist. Quart. 26(4):643–650.Crossref, Google Scholar
• Ingargiola G, Korsh JF (1975) An algorithm for the solution of 0-1 loading problems. Oper. Res. 23(6):1110–1119.Link, Google Scholar
• Kataoka S, Yamada T (2014) Upper and lower bounding procedures for the multiple knapsack assignment problem. Eur. J. Oper. Res. 237(2):440–447.Google Scholar
• Klose A, Görtz S (2007) A branch-and-price algorithm for the capacitated facility location problem. Eur. J. Oper. Res. 179(3):1109–1125.Crossref, Google Scholar
• Laaloui Y (2013) Improved swap heuristic for the multiple knapsack problem. Rojas IGJ, Joya G, eds. Advances in Computational Intelligence, vol. 7902 of Lecture Notes in Computer Science (Springer, Berlin), 547–555.Crossref, Google Scholar
• Laaloui Y, M’Hallah R (2016) A binary multiple knapsack model for single machine scheduling with machine unavailability. Comput. Oper. Res. 72:71–82.Crossref, Google Scholar
• Lalami ME, Elkihel M, El Baz D, Boyer V (2012) A procedure-based heuristic for the 0-1 multiple knapsack problems. Internat. J. Oper. Res. 4(3):214–224.Crossref, Google Scholar
• Loti de Lima V, Alves C, Clautiaux F, Iori M, Valério de Carvalho JM (2022) Arc flow formulations based on dynamic programming: Theoretical foundations and applications. Eur. J. Oper. Res. 296(1):3–21.Crossref, Google Scholar
• Martello S, Toth P (1980) Solution of the zero-one multiple knapsack problem. Eur. J. Oper. Res. 4(4):276–283.Crossref, Google Scholar
• Martello S, Toth P (1981a) A bound and bound algorithm for the zero-one multiple knapsack problem. Discrete Appl. Math. 3(4):275–288.Crossref, Google Scholar
• Martello S, Toth P (1981b) Heuristic algorithms for the multiple knapsack problem. Computing 27:93–112.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (Wiley, New York).Google Scholar
• Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Sci. 45(3):414–424.Link, Google Scholar
• Pisinger D (1999) An exact algorithm for large multiple knapsack problems. Eur. J. Oper. Res. 114(3):528–541.Crossref, Google Scholar
• Valério de Carvalho JM (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86:629–659.Crossref, Google Scholar
• Valério de Carvalho JM (2002) LP models for bin packing and cutting stock problems. Eur. J. Oper. Res. 141:253–273.Crossref, Google Scholar
• Valério de Carvalho JM (2005) Using extra dual cuts to accelerate column generation. INFORMS J. Comput. 17:175–182.Link, Google Scholar
• Wolsey L (1998) Integer Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar