A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem

References

• Beasley JE (1990) A lagrangian heuristic for set-covering problems. Naval Res. Logist. 37(1):151–164.Crossref, Google Scholar
• Chen L, Khan S, Li KF, Manning EG (1999) Building an adaptive multimedia system using the utility model. Rolim J, Mueller F, Zomaya AY, Ercal F, Olariu S, Ravindran B, Gustafsson J, et al., eds. Proc. Internat. Parallel Processing Sympos. (Springer, Berlin, Heidelberg), 289–298.Google Scholar
• Chen Y, Hao JK (2014) A reduce and solve approach for the multiple-choice multidimensional knapsack problem. Eur. J. Oper. Res. 239(2):313–322.Crossref, Google Scholar
• Cherfi N, Hifi M (2010) A column generation method for the multiple-choice multi-dimensional knapsack problem. Comput. Optim. Appl. 46(1):51–73.Crossref, Google Scholar
• Crévits I, Hanafi S, Mansi R, Wilbaut C (2012) Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem. Comput. Oper. Res. 39(1):32–41.Crossref, Google Scholar
• Driebeek NJ (1966) An algorithm for the solution of mixed integer programming problems. Management Sci. 12(7):576–587.Link, Google Scholar
• Ghasemi T, Razzazi M (2011) Development of core to solve the multidimensional multiple-choice knapsack problem. Comput. Indust. Engrg. 60(2):349–360.Crossref, Google Scholar
• Hanafi S, Mansi R, Wilbaut C (2009) Iterative relaxation-based heuristics for the multiple-choice multidimensional knapsack problem. Blesa MJ, Blum C, Di Gaspero L, Roli A, Sampels M, Schaerf A, eds. Hybrid Metaheuristics HM 2009, Theoretical Computer Science and General Issues, vol. 5818 (Springer, Berlin, Heidelberg), 73–83.Google Scholar
• Hifi M, Wu L (2012) An equivalent model for exactly solving the multiple-choice multidimensional knapsack problem. Internat. J. Combin. Optim. Problems Informatics 3(3):43–58.Google Scholar
• Hifi M, Wu L (2014) Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem. Engrg. Optim. 47(12):1619–1636.Crossref, Google Scholar
• Hifi M, Michrafy M, Sbihi A (2004a) Heuristic algorithms for the multiple-choice multidimensional knapsack problem. J. Oper. Res. Soc. 55(12):1323–1332.Crossref, Google Scholar
• Hifi M, Sadfi S, Sbihi A (2004b) An exact algorithm for the multiple-choice multidimensional knapsack problem. Les Cahiers de la Maison des Sciences Economiques: Série bleue, 24 (Université Panthéon-Sorbonne, Paris).Google Scholar
• Hifi M, Michrafy M, Sbihi A (2006) A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem. Comput. Optim. Appl. 33(2–3):271–285.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Introduction to NP-completeness of knapsack problems. Knapsack Problems (Springer, Berlin), 483–493.Crossref, Google Scholar
• Khan MS (1998) Quality adaptation in a multisession multimedia system: Model, algorithms and architecture. PhD thesis, Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada.Google Scholar
• Khan S, Li KF, Manning EG, Akbar MM (2002) Solving the knapsack problem for adaptive multimedia systems. Stud. Inform. Univ. 2(1):157–178.Google Scholar
• Lee C, Lehoezky J, Rajkumar R, Siewiorek D (1999) On quality of service optimization with discrete qos options. Proc. 5th IEEE Real-Time Tech. Appl. Sympos. (IEEE, Washington, DC), 276–286.Google Scholar
• Mansi R, Alves C, Valerio de Carvalho J, Hanafi S (2013) A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engrg. Optim. 45(8):983–1004.Crossref, Google Scholar
• Mansini R, Speranza M (2002) A multidimensional knapsack model for asset-backed securitization. J. Oper. Res. Soc. 53(8):822–832.Crossref, Google Scholar
• Mansini R, Speranza MG (2012) Coral: An exact algorithm for the multidimensional knapsack problem. INFORMS J. Comput. 24(3):399–415.Link, Google Scholar
• Moser M, Jokanovic D, Shiratori N (1997) An algorithm for the multidimensional multiple-choice knapsack problem. IEICE Trans. Fundamentals Electronics Comm. Comput. Sci. 80(3):582–589.Google Scholar
• Oliva C, Michelon P, Artigues C (2001) Constraint and linear programming: Using reduced costs for solving the zero/one multiple knapsack problem. Proc. Workshop Cooperative Solvers Constraint Programming, Paphos, Cyprus, 87–98.Google Scholar
• Sbihi A (2007) A best first search exact algorithm for the multiple-choice multidimensional knapsack problem. J. Combin. Optim. 13(4):337–351.Crossref, Google Scholar
• Shojaei H, Basten T, Geilen M, Davoodi A (2013) A fast and scalable multidimensional multiple-choice knapsack heuristic. ACM Trans. Design Automation Electronic Systems 18(4):51:1–51:32.Google Scholar
• Toyoda Y (1975) A simplified algorithm for obtaining approximate solutions to zero-one programming problems. Management Sci. 21(12):1417–1427.Link, Google Scholar
• Van de Velde S, Worm J (1994) Multi-period planning of road maintenance: A multiple-choice multi-knapsack problem. Technical Report LPOM-94-6, Department of Mechanical Engineering, University of Twente, Enschede, Netherlands.Google Scholar
• Watson R (2001) Packet networks and optimal admission and upgrade of service level agreements: Applying the utility model. MSc thesis, ECE, University of Victoria, Victoria, BC, Canada.Google Scholar
• Wilbaut C, Hanafi S (2009) New convergent heuristics for 0–1 mixed integer programming. Eur. J. Oper. Res. 195(1):62–74.Crossref, Google Scholar
• Ykman-Couvreur C, Nollet V, Catthoor F, Corporaal H (2006) Fast multi-dimension multi-choice knapsack heuristic for mp-soc run-time management. Proc. 2006 Internat. Sympos. System-on-Chip (IEEE, Washington, DC), 1–4.Google Scholar