The multi-dimensional multiple-choice knapsack problem (MMKP) is among the most challenging combinatorial optimization problems. MMKP is an NP-complete problem and exact solutions for MMKP are often not tractable in practice. Heuristics solutions are therefore often applied. Methods to solve MMKP instances can be categorized into two classes: heuristics to generate high quality solutions for larger problem instances, and fast algorithms to solve MMKP instances in real time, giving up some solution quality.

The following are references to our work on a scalable MMKP heuristic

  • H. Shojaei, T. Basten, M.C.W. Geilen, A. Davoodi. A Fast and Scalable Multi-dimensional Multiple-choice Knapsack Heuristic. ACM Transactions on Design Automation of Electronic Systems, ToDAES. 18(4), Article 51, 32 pages, October 2013. (pdf / doi) 2015 ACM TODAES best paper. See 52nd DAC Awards. © The authors, 2013. Publication rights licensed to ACM.
  • H. Shojaei, A.H. Ghamarian, T. Basten, M.C.W. Geilen, S. Stuijk. R. Hoes. A Parameterized Compositional Multi-dimensional Multiple-choice Knapsack Heuristic for CMP Run-time Management. In 46th Design Automation Conference, DAC 2009, Proceedings, pages 917-922. San Francisco, California, USA, 26-31 July, 2009. ACM Press, New York, NY, USA, 2009.

Click on MMKP Benchmarks for Additional, Irregular Multi-dimensional Multiple-choice Knapsack Problem (MMKP) Benchmarks.

Click on Implementation for our MMKP heuristic algorithm implementation.

To contact us: e-mail:

Part of this work was supported by the EC through FP7 IST project 216224, MNEMEE.