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