Yuning Chen and Jin-Kao Hao. "A "reduce and solve" approach for the multiple-choice multidimensional knapsack problem". European Journal of Operational Research. 239(2): 313-322, 2014.

The source code is here. To compile this source code, the CPLEX software should be firstly installed in your machine. Please make sure that the above paper is cited if you use the code in your research.  The software is distributed for academic puposes only. If you wish to use this software for commercial applications, please obtain a permission from Yuning Chen (yuning@info.univ-angers.fr) or Jin-Kao Hao (hao@info.univ-angers.fr).

### Problem definition (Informal)

We are given a set of items that are divided into several groups and different types of limited resources. Each item requires a certain amount of each resource and generates a profit. The purpose of the MMKP is to select exactly one item from each group such that the total profit of the selected items is maximized while the consumption of each resource does not exceed the given limit (knapsack constraints).

### Instance files

Instances I07-I13 and INST01-INST20 are classical benchmark instances which can be downloaded from here. INST21-INST30 are instances with irregular structures where the number of items per group varies. The original data files of these irregular instances are available at http://www.es.ele.tue.nl/pareto/mmkp/. In order to standarize the input files for our implemented program, we modified the format of these instances as follows. For each instance, we first identify a group whose number of items is the maximum among all the groups, we then extend the other groups to reach this number of items by filling, for each of them, with the missing number of columns (items) with a profit value of 0 and a very large weight for each dimension (resource) which is larger than the capacity of the corresponding resource. When such a modified instance is solved by CPLEX, the artificially added columns will be definitely eliminated in the preprocessing step, which doesn't affect the effectiveness of our approach. The modified instances can be downloaded from here. Meanwhile, The solution certificates in the following table (Table 1) are associated with the modified instances.

### Input file format

The format of the input data files is:

 n (number of groups) l (number of items in each group) m (number of different resources) R_1 R_2 ......... R_m (Available resources: from resource 1 to resource m) 1 (Data of group 1) p_11 (profit of item 1) r_111 r_112 ..... r_11m (Resource consumption by item 1) p_12 (profit of item 2) r_211 r_212 ..... r_21m (Resource consumption by item 2) . . p_1l (profit of item l) r_1l1 r_1l2 ..... r_1lm (Resource consumption by item l) 2 ......................... ......................... ......................... n ......................... ......................... ......................... 

### Output file format

The format of the solution file is:
 Objective value \rho_1 \rho_2 ......... \rho_n (index of the selected item of each group) 

### Best results and solution certificates

Table1. Best results reported in the above paper.