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 ( or Jin-Kao Hao (

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 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)

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. 

Instance Best res. Certificate Instance Best res. Certificate
I07 24595 Click here INST14 32875 Click here
I08 36894 Click here INST15 39163 Click here
I09 49185 Click here INST16 43367 Click here
I10 61478 Click here INST17 54363 Click here
I11 73791 Click here INST18 60467 Click here
I12 86095 Click here INST19 64932 Click here
I13 98441 Click here INST20 75616 Click here
INST01 10738 Click here INST21 44280 Click here
INST02 13598 Click here INST22 41966 Click here
INST03 10947 Click here INST23 42584 Click here
INST04 14456 Click here INST24 41860 Click here
INST05 17061 Click here INST25 44159 Click here
INST06 16840 Click here INST26 44879 Click here
INST07 16444 Click here INST27 87630 Click here
INST08 17514 Click here INST28 134648 Click here
INST09 17763 Click here INST29 179228 Click here
INST10 19316 Click here INST30 214230 Click here
INST11 19449 Click here - - -
INST12 21741 Click here - - -
INST13 21578 Click here - - -