Implementation of simulated annealing algorithm for the multiple choice multidimensional knapsack problem. The multiple choice knapsack problem has n groups of items and m constraints. The objective is to choose one item from each group such that the total value (profit) is maximized while all of the m constraints are satisfied.
The implementation is quite fast, and the code finds optimum or very close to optimum solutions in a very short duration.
Usage:
- Compile the code using g++ - e.g. g++ saMultiChoiceKnapsack.cpp - Run ./a.out filename iterations - e.g. ./a.out instances/I01 100000
Instances are available at the following FTP site and also in the instances folder:
ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/MMKP/
ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/MMKP/MMKP.html
Cite this code:
@misc{shah2014mcknapsack,
title={Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem},
author={Shah, Shalin},
year={2020},
DOI={10.5281/zenodo.3820939}
}
Cited By:
- Heikal, A. F., et al. "A New Genetic Algorithm for Multiple-Choice Multidimensional Knapsack Problem." The International Conference on Electrical Engineering. Vol. 7. No. 7th International Conference on Electrical Engineering ICEENG 2010. Military Technical College, 2010.
Results:
Results on some instances (from the instances directory and at the above mentioned FTP site). The algorithm is quite fast and takes only a few seconds for 100000 iterations). The code is able to find optimum solutions for almost all instances (or at least a close to optimum solution)
| Instance | Best Known Solution | This Algorithm's Solution |
| I01 | 173 | 173 |
| I02 | 364 | 361 |
| I03 | 1602 | 1595 |
| I04 | 3597 | 3542 |
| I05 | 3905 | 3900 |
| I06 | 4799 | 4792 |
| I07 | 23912 | 24225 |
| I08 | 35979 | 36283 |
| I09 | 47901 | 48308 |
| I10 | 59811 | 60419 |
| I11 | 71760 | 72494 |
| I12 | 84141 | 84615 |
| I13 | 96003 | 96791 |