CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem

References

• Angelelli E., Mansini R., Speranza M. G. Kernel search: A general heuristic for the multi-dimensional knapsack problem. Comput. Oper. Res. (2010) 37(11):2017–2026Crossref, Google Scholar
• Balas E., Zemel E. An algorithm for large zero-one knapsack problems. Oper. Res. (1980) 28(5):1130–1154Link, Google Scholar
• Boussier S., Vasquez M., Vimont Y., Hanafi S., Michelon P. Solving the 0-1 multidimensional knapsack problem with resolution search. VI ALIO/EURO Workshop Appl. Combin. Optim., Buenos Aires (2008) . Computing Research Repository Article abs/0905.0848Google Scholar
• Chu P. C., Beasley J. E. A genetic algorithm for the multidimensional knapsack problem. J. Heuristics (1998) 4(1):63–86Crossref, Google Scholar
• Chvátal V. Resolution search. Discrete Appl. Math. (1997) 73(1):81–99Crossref, Google Scholar
• Fayard D., Plateau G. An algorithm for the solution of the 0-1 knapsack problem. Computing (1982) 28:269–287Crossref, Google Scholar
• Fréville A., Plateau G. An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem. Discrete Appl. Math. (1994) 49(1–3):189–212Crossref, Google Scholar
• Gavish B., Pirkul H. Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming (1985) 31(1):78–105Crossref, Google Scholar
• Glover F., Kochenberger G. A., Osman I. H., Kelly J. P. Critical event tabu search for multidimensional knapsack problems. Meta-Heuristics: Theory and Applications (1996) (Kluwer Academic Publishers, Boston) 407–427Crossref, Google Scholar
• Hanafi S., Wilbaut C. Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Ann. Oper. Res. (2011) 183(1):125–142Crossref, Google Scholar
• Huston S., Puchinger J., Stuckey P. J., Harland J., Manyem P. The core concept for 0/1 integer programming. Proc. 14th Comput.: Australasian Theory Sympos. (CRPIT 77) (2008) (Australian Computer Society, Sydney, NSW) 39–47Google Scholar
• Kaparis K., Letchford A. N. Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem. Eur. J. Oper. Res. (2008) 186(1):91–103Crossref, Google Scholar
• Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer, Berlin) Crossref, Google Scholar
• Mansini R., Speranza M. G. A multidimensional knapsack model for asset-backed securitization. J. Oper. Res. Soc. (2002a) 53(8):822–832Crossref, Google Scholar
• Mansini R., Speranza M. G. Multi-unit combinatorial auctions: An exact approach. Proc. 5th Internat. Conf. Electronic Commerce Res. (ICECR-5) (2002b) Montréal(HEC, University of Montréal, Montréal) . CD-ROMGoogle Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, New York) Google Scholar
• Martello S., Toth P. An exact algorithm for the two-constraint 0-1 knapsack problem. Oper. Res. (2003) 51(5):826–835Link, Google Scholar
• Oliva C., Michelon P., Artigues C. Constraint and linear programming: Using reduced costs for solving the zero/one multiple knapsack problem. Proc. Workshop Cooperative Solvers Constraint Programming (CoSolv 01) (2001) Paphos, Cyprus:87–98Google Scholar
• Pisinger D. Core problems in knapsack algorithms. Oper. Res. (1999) 47(4):570–575Link, Google Scholar
• Puchinger J., Raidl G. R., Pferschy U. The multidimensional knapsack problem: Structure and algorithms. INFORMS J. Comput. (2010) 22(2):250–265Link, Google Scholar
• Shih W. A branch and bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. (1979) 30(4):369–378Crossref, Google Scholar
• Vasquez M., Hao J. K. An hybrid approach for the 0-1 multidimensional knapsack problem. Proc. 17th Internat. Joint Conf. Artificial Intelligence (IJCAI-01) (2001) (Morgan Kaufmann, San Francisco) 328–333Google Scholar
• Vasquez M., Vimont Y. Improved results on the 0-1 multidimensional knapsack problem. Eur. J. Oper. Res. (2005) 165(1):70–81Crossref, Google Scholar
• Vimont Y., Boussier S., Vasquez M. Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem. J. Combin. Optim. (2008) 15(2):165–178Crossref, Google Scholar
• Wilbaut C., Hanafi S. New convergent heuristics for 0-1 mixed integer programming. Eur. J. Oper. Res. (2009) 195(1):62–74Crossref, Google Scholar