More Web Proxy on the site http://driver.im/

research-article

A fast and scalable multidimensional multiple-choice knapsack heuristic

Authors:

Azadeh DavoodiAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 18, Issue 4

Article No.: 51, Pages 1 - 32

https://doi.org/10.1145/2541012.2541014

Published: 25 October 2013 Publication History

Abstract

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.

References

[1]

Akbar, M. M., Rahman, M. S., Kaykobad, M., Manning, E. G., and Shoja, G. C. 2006. Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls. Comput. Oper. Res. 33, 5, 1259--1273.

Digital Library

[2]

Bentley, J. 1980. Multidimensional divide-and-conquer. Comm. ACM 23, 214--229.

Digital Library

[3]

Borzsonyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the IEEE Conference on Data Engineering. IEEE, 421--430.

Digital Library

[4]

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.

Digital Library

[5]

Cherfi, N. 2009. Hybrid algorithms for knapsack problems. Ph.D. thesis, University of Paris I, France.

[6]

Cherfi, N. and Hifi, M. 2008. A column generation method for the multiple-choice multi-dimensional knapsack problem. Comput. Optim. Appl. 46, 1, 51--73.

Digital Library

[7]

Cherfi, N. and Hifi, M. 2009. Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem. Int. J. Operational Research 5, 1, 89--109.

[8]

Cplex 2012. IBM ILOG Cplex. http://www-01.ibm.com/software/websphere/products/optimization/academic-initiative/.

[9]

Crévits, I., Hanafi, S., Mansi, R., and Wilbaut, C. 2012. Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem. Comput. Operations Research 39, 32--41.

Digital Library

[10]

Dai, K.-R., Liu, W.-H., and Li, Y.-L. 2012. NCTU-GR: Efficient simulated evolution-based rerouting and congestion-relaxed layer assignment on 3-d global routing. IEEE Trans. VLSI Syst. 20, 3, 459--472.

Digital Library

[11]

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.

Digital Library

[12]

Geilen, M., Basten, T., Theelen, B. D., and Otten, R. 2005. An algebra of Pareto points. In Proceedings of the 5th International Conference on Application of Concurrency to System Design (ACSD'05). IEEE, 88--97.

Digital Library

[13]

Geilen, M., Basten, T., Theelen, B. D., and Otten, R. 2007. An algebra of Pareto points. Fundamenta Informaticae 78, 1, 35--74.

Digital Library

[14]

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.

Digital Library

[15]

Hanafi, S., Mansi, R., and Wilbaut, C. 2009. Iterative relaxation-based heuristics for the multiple-choice multidimensional knapsack problem. In Proceedings of the 6th International Workshop on Hybrid Metaheuristics, Lecture Notes in Computer Science, vol. 5818, 73--83.

Digital Library

[16]

Hifi, M., Michrafy, M., and Sbihi, A. 2004. Heuristic algorithms for the multiple-choice multidimensional knapsack problem. J. Operational Research Soc. 55, 12, 1323--1332.

[17]

Hifi, M., Michrafy, M., and Sbihi, A. 2006. A reactive local search-based algorithm for the multiple-choice multidimensional knapsack problem. Comput. Optim. Appl. 33, 2--3, 271--285.

Digital Library

[18]

Hiremath, C. S. and Hill, R. R. 2007. New greedy heuristics for the multiple-choice multi-dimensional knapsack problem. Int. J. Operational Research 2, 4, 495--512.

[19]

Hu, J., Roy, J., and Markov, I. 2010. Completing high-quality global routes. In Proceedings of the International Symposium on Physical Design. ACM, 35--41.

Digital Library

[20]

ISPD Contests 2007, 2008. http://www.ispd.cc/contests/.

[21]

Khan, S. 1998. Quality adaptation in a multisession multimedia system: Model, algorithms and architecture. Ph.D. thesis, Univ. of Victoria, Victoria, B.C., Canada.

Digital Library

[22]

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.

[23]

Kung, H., Luccio, F., and Preparata, F. 1975. On finding the maxima of a set of vectors. J. ACM 22, 469--476.

Digital Library

[24]

MMKP Benchmarks. 2010. MMKP benchmarks. ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/MMKP/MMKP.html.

[25]

MMKP Benchmarks. 2012. MMKP benchmarks. http://www.es.ele.tue.nl/pareto/mmkp/.

[26]

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.

[27]

Parra-Hernandez, R. and Dimopoulos, N. J. 2005. A new heuristic for solving the multichoice multidimensional knapsack problem. IEEE Trans. Syst. Man Cybernetics, Part A 35, 5, 708--717.

Digital Library

[28]

Pisinger, D. 1995. Algorithms for knapsack problems. Ph.D. thesis, DIKU, University of Copenhagen, Denmark.

[29]

Preparata, F. and Shamos, M. 1985. Computational Geometry: An Introduction. Springer.

Digital Library

[30]

Sbihi, A. 2003. Hybrid methods in combinatorial optimization: Exact algorithms and heuristics. Ph.D. thesis, Univ. of Paris I, France.

[31]

Sbihi, A. 2007. A best first search exact algorithm for the multiple-choice multidimensional knapsack problem. J. Comb. Optim. 13, 4, 337--351.

[32]

Shojaei, H., Ghamarian, A., Basten, T., Geilen, M., Stuijk, S., and Hoes, R. 2009. A parameterized compositional multi-dimensional multiple-choice knapsack heuristic for CMP run-time management. In Proceedings of the IEEE/ACM Design Automation Conference. ACM, 917--922.

Digital Library

[33]

Shojaei, H., Wu, T.-H., Davoodi, A., and Basten, T. 2010. A Pareto-algebraic framework for signal power optimization in global routing. In Proceedings of the International Symposium on Low-Power Electronics and Design. ACM. 407--412.

Digital Library

[34]

Simit-ARM 2012. SimIt-ARM. http://simit-arm.sourceforge.net.

[35]

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.

Digital Library

[36]

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.

Digital Library

[37]

Ykman-Couvreur, C., Nollet, V., Catthoor, F., and Corporaal, H. 2011. Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management. ACM Trans. Embed. Comput. Syst. 10, 3, Article 35.

Digital Library

[38]

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.

[39]

Yukish, M. 2004. Algorithms to identify Pareto points in multi-dimensional data sets. Ph.D. thesis, Pennsylvania State University.

Digital Library

Cited By

Su QZhang QLi WZhang X(2023)Primal-Dual-Based Computation Offloading Method for Energy-Aware Cloud-Edge CollaborationIEEE Transactions on Mobile Computing10.1109/TMC.2023.3237938(1-15)Online publication date: 2023
https://doi.org/10.1109/TMC.2023.3237938
Yang JKim YYoon Y(2022)A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack ProblemMathematics10.3390/math1004060210:4(602)Online publication date: 16-Feb-2022
https://doi.org/10.3390/math10040602
Mancini SMeloni CCiavotta M(2022)A decomposition approach for multidimensional knapsacks with family‐split penaltiesInternational Transactions in Operational Research10.1111/itor.1320731:4(2247-2271)Online publication date: 8-Sep-2022
https://doi.org/10.1111/itor.13207
Show More Cited By

Index Terms

A fast and scalable multidimensional multiple-choice knapsack heuristic

Recommendations

Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls

This paper presents a heuristic to solve the Multidimensional Multiple-choice Knapsack Problem (MMKP), a variant of the classical 0-1 Knapsack Problem. We apply a transformation technique to map the multidimensional resource consumption to single ...
Multistart solution-based tabu search for the Set-Union Knapsack Problem
Abstract
The NP-hard Set-Union Knapsack Problem is a general model able to formulate a number of practical problems. As a variant of the popular knapsack problem, SUKP is to find a subset of candidate items (an item is composed of several ...
Highlights
- The Set-Union Knapsack problem is a relevant model for many practical decision and optimization problems.
Development of core to solve the multidimensional multiple-choice knapsack problem

The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0-1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not been developed for the MMKP so far. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 18, Issue 4

Special Section on Networks on Chip: Architecture, Tools, and Methodologies

October 2013

380 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2541012

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 25 October 2013

Accepted: 01 April 2013

Revised: 01 March 2013

Received: 01 August 2012

Published in TODAES Volume 18, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Seventh Framework Programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
493
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)7

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Su QZhang QLi WZhang X(2023)Primal-Dual-Based Computation Offloading Method for Energy-Aware Cloud-Edge CollaborationIEEE Transactions on Mobile Computing10.1109/TMC.2023.3237938(1-15)Online publication date: 2023
https://doi.org/10.1109/TMC.2023.3237938
Yang JKim YYoon Y(2022)A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack ProblemMathematics10.3390/math1004060210:4(602)Online publication date: 16-Feb-2022
https://doi.org/10.3390/math10040602
Mancini SMeloni CCiavotta M(2022)A decomposition approach for multidimensional knapsacks with family‐split penaltiesInternational Transactions in Operational Research10.1111/itor.1320731:4(2247-2271)Online publication date: 8-Sep-2022
https://doi.org/10.1111/itor.13207
Dellinger ALu YSong MVasko F(2022)Simple strategies that generate bounded solutions for the multiple‐choice multi‐dimensional knapsack problem: a guide for OR practitionersInternational Transactions in Operational Research10.1111/itor.1314430:6(4061-4077)Online publication date: 11-Apr-2022
https://doi.org/10.1111/itor.13144
Lamanna LMansini RZanotti R(2022)A two-phase kernel search variant for the multidimensional multiple-choice knapsack problemEuropean Journal of Operational Research10.1016/j.ejor.2021.05.007297:1(53-65)Online publication date: Feb-2022
https://doi.org/10.1016/j.ejor.2021.05.007
Bentsen HHoff AHvattum L(2022)Exponential extrapolation memory for tabu searchEURO Journal on Computational Optimization10.1016/j.ejco.2022.10002810(100028)Online publication date: 2022
https://doi.org/10.1016/j.ejco.2022.100028
Cacchiani VIori MLocatelli AMartello S(2022)Knapsack problems — An overview of recent advances. Part IIComputers and Operations Research10.1016/j.cor.2021.105693143:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105693
Zhang MWang FZhu YLiu JWang ZAlay ÖHsu CBegen A(2021)Towards cloud-edge collaborative online video analytics with fine-grained serverless pipelinesProceedings of the 12th ACM Multimedia Systems Conference10.1145/3458305.3463377(80-93)Online publication date: 24-Jun-2021
https://dl.acm.org/doi/10.1145/3458305.3463377
Bayhan SMaghsudi SZubow A(2021)EdgeDASH: Exploiting Network-Assisted Adaptive Video Streaming for Edge CachingIEEE Transactions on Network and Service Management10.1109/TNSM.2020.303714718:2(1732-1745)Online publication date: Jun-2021
https://doi.org/10.1109/TNSM.2020.3037147
Sau CRinaldi CPomante LPalumbo FValente GFanni TMartinez Mvan der Linden FBasten TGeilen MPeeren GKadlec JJääskeläinen PBulej LBarranco FSaarinen JSäntti TZedda MSanchez VNikkhah SGoswami DAmat GMaršík Lvan Helvoort MMedina LAl-Ars Zde Beer A(2021)Design and management of image processing pipelines within CPSMicroprocessors & Microsystems10.1016/j.micpro.2021.10435087:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.micpro.2021.104350
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents