{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T13:57:40Z","timestamp":1780408660818,"version":"3.54.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>Many combinatorial optimization problems in the embedded systems and design automation domains involve decision making in multidimensional spaces. The multidimensional multiple-choice knapsack problem (MMKP) is among the most challenging of the encountered optimization problems. MMKP problem instances appear for example in chip multiprocessor runtime resource management and in global routing of wiring in circuits. Chip multiprocessor resource management requires solving MMKP under real-time constraints, whereas global routing requires scalability of the solution approach to extremely large MMKP instances. This article presents a novel MMKP heuristic, CPH (for Compositional Pareto-algebraic Heuristic), which is a parameterized compositional heuristic based on the principles of Pareto algebra. Compositionality allows incremental computation of solutions. The parameterization allows tuning of the heuristic to the problem at hand. These aspects make CPH a very versatile heuristic. When tuning CPH for computation time, MMKP instances can be solved in real time with better results than the fastest MMKP heuristic so far. When tuning CPH for solution quality, it finds several new solutions for standard benchmarks that are not found by any existing heuristic. CPH furthermore scales to extremely large problem instances. We illustrate and evaluate the use of CPH in both chip multiprocessor resource management and in global routing.<\/jats:p>","DOI":"10.1145\/2541012.2541014","type":"journal-article","created":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T14:09:19Z","timestamp":1383746959000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["A fast and scalable multidimensional multiple-choice knapsack heuristic"],"prefix":"10.1145","volume":"18","author":[{"given":"Hamid","family":"Shojaei","sequence":"first","affiliation":[{"name":"University of Wisconsin - Madison, WI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Twan","family":"Basten","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marc","family":"Geilen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Azadeh","family":"Davoodi","sequence":"additional","affiliation":[{"name":"University of Wisconsin - Madison, WI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,10,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.09.016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the IEEE Conference on Data Engineering. IEEE, 421--430","author":"Borzsonyi S.","unstructured":"Borzsonyi , S. , Kossmann , D. , and Stocker , K . 2001. The skyline operator . In Proceedings of the IEEE Conference on Data Engineering. IEEE, 421--430 . Borzsonyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the IEEE Conference on Data Engineering. IEEE, 421--430."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 338--343","author":"Chang Y.-J.","unstructured":"Chang , Y.-J. , Lee , Y.-T. , and Wang , T . -C. 2008. NTHU-Route 2.0: a fast and stable global router . In Proceedings of the IEEE International Conference on Computer-Aided Design. 338--343 . Chang, Y.-J., Lee, Y.-T., and Wang, T.-C. 2008. NTHU-Route 2.0: a fast and stable global router. In Proceedings of the IEEE International Conference on Computer-Aided Design. 338--343."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-008-9184-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJOR.2009.024531"},{"key":"e_1_2_1_8_1","unstructured":"Cplex 2012. IBM ILOG Cplex. http:\/\/www-01.ibm.com\/software\/websphere\/products\/optimization\/academic-initiative\/.  Cplex 2012. IBM ILOG Cplex. http:\/\/www-01.ibm.com\/software\/websphere\/products\/optimization\/academic-initiative\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.12.016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2010.2102780"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. IEEE, 285--290","author":"Geilen M.","unstructured":"Geilen , M. and Basten , T . 2007. A calculator for Pareto points . In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. IEEE, 285--290 . Geilen, M. and Basten, T. 2007. A calculator for Pareto points. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. IEEE, 285--290."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2005.2"},{"key":"e_1_2_1_13_1","first-page":"35","article-title":"An algebra of Pareto points","volume":"78","author":"Geilen M.","year":"2007","unstructured":"Geilen , M. , Basten , T. , Theelen , B. D. , and Otten , R. 2007 . An algebra of Pareto points . Fundamenta Informaticae 78 , 1, 35 -- 74 . Geilen, M., Basten, T., Theelen, B. D., and Otten, R. 2007. An algebra of Pareto points. Fundamenta Informaticae 78, 1, 35--74.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 31st International Conference on Very Large Databases. VLDB Endowment, 229--240","author":"Godfrey P.","unstructured":"Godfrey , P. , Shipley , R. , and Gryz , J . 2005. Maximal vector computation in large data sets . In Proceedings of the 31st International Conference on Very Large Databases. VLDB Endowment, 229--240 . Godfrey, P., Shipley, R., and Gryz, J. 2005. Maximal vector computation in large data sets. In Proceedings of the 31st International Conference on Very Large Databases. VLDB Endowment, 229--240."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04918-7_6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601796"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-005-3057-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJOR.2007.014176"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735035"},{"key":"e_1_2_1_20_1","unstructured":"ISPD Contests 2007 2008. http:\/\/www.ispd.cc\/contests\/.  ISPD Contests 2007 2008. http:\/\/www.ispd.cc\/contests\/."},{"key":"e_1_2_1_22_1","first-page":"157","article-title":"Solving the knapsack problem for adaptive multimedia systems","volume":"2","author":"Khan S.","year":"2002","unstructured":"Khan , S. , Li , K. F. , Manning , E. G. , and Akbar , M. M. 2002 . Solving the knapsack problem for adaptive multimedia systems . Stud. Inform. Univ. 2 , 1, 157 -- 178 . Khan, S., Li, K. F., Manning, E. G., and Akbar, M. M. 2002. Solving the knapsack problem for adaptive multimedia systems. Stud. Inform. Univ. 2, 1, 157--178.","journal-title":"Stud. Inform. Univ."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_1_24_1","unstructured":"MMKP Benchmarks. 2010. MMKP benchmarks. ftp:\/\/cermsem.univ-paris1.fr\/pub\/CERMSEM\/hifi\/MMKP\/MMKP.html.  MMKP Benchmarks. 2010. MMKP benchmarks. ftp:\/\/cermsem.univ-paris1.fr\/pub\/CERMSEM\/hifi\/MMKP\/MMKP.html."},{"key":"e_1_2_1_25_1","unstructured":"MMKP Benchmarks. 2012. MMKP benchmarks. http:\/\/www.es.ele.tue.nl\/pareto\/mmkp\/.  MMKP Benchmarks. 2012. MMKP benchmarks. http:\/\/www.es.ele.tue.nl\/pareto\/mmkp\/."},{"key":"e_1_2_1_26_1","first-page":"582","article-title":"An algorithm for the multidimensional multiple-choice knapsack problem","volume":"80","author":"Moser M.","year":"1997","unstructured":"Moser , M. , Jokanovic , D. P. , and Shiratori , N. 1997 . An algorithm for the multidimensional multiple-choice knapsack problem . IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 80 , 3, 582 -- 589 . Moser, M., Jokanovic, D. P., and Shiratori, N. 1997. An algorithm for the multidimensional multiple-choice knapsack problem. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 80, 3, 582--589.","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCA.2005.851140"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-9035-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630147"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1840845.1840935"},{"key":"e_1_2_1_34_1","unstructured":"Simit-ARM 2012. SimIt-ARM. http:\/\/simit-arm.sourceforge.net.  Simit-ARM 2012. SimIt-ARM. http:\/\/simit-arm.sourceforge.net."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE, 250--255","author":"Xu Y.","unstructured":"Xu , Y. and Chu , C . 2011. MGR: Multi-level global router . In Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE, 250--255 . Xu, Y. and Chu, C. 2011. MGR: Multi-level global router. In Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE, 250--255."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference. 576--581","author":"Xu Y.","unstructured":"Xu , Y. , Zhang , Y. , and Chu , C . 2009. Fastroute 4.0: global router with efficient via minimization . In Proceedings of the Asia and South Pacific Design Automation Conference. 576--581 . Xu, Y., Zhang, Y., and Chu, C. 2009. Fastroute 4.0: global router with efficient via minimization. In Proceedings of the Asia and South Pacific Design Automation Conference. 576--581."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1952522.1952528"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the International Symposium on System-on-Chip. IEEE, 1--4.","author":"Ykman-Couvreur C.","unstructured":"Ykman-Couvreur , C. , Nollet , V. , Marescaux , T. , Brockmeyer , E. , Catthoor , F. , and Corp oraal, H . 2006. Fast multi-dimension multi-choice knapsack heuristic for MP-SoC run-time management . In Proceedings of the International Symposium on System-on-Chip. IEEE, 1--4. Ykman-Couvreur, C., Nollet, V., Marescaux, T., Brockmeyer, E., Catthoor, F., and Corporaal, H. 2006. Fast multi-dimension multi-choice knapsack heuristic for MP-SoC run-time management. In Proceedings of the International Symposium on System-on-Chip. IEEE, 1--4."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541012.2541014","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2541012.2541014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:54Z","timestamp":1750234194000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2541012.2541014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2541012.2541014"],"URL":"https:\/\/doi.org\/10.1145\/2541012.2541014","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}