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.

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