Yuning Chen and Jin-Kao Hao. "Iterated Responsive Threshold Search for the Quadratic Multiple Knapsack Problem". Annals of Operations Research. August 2014.
The solution certificats of the best results reported in the paper are be available here. The
source code of the IRTS algorithm is available upon request.
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)
Let N={1,2,...,n}$ be a set of n
objects and M={1,2,...,m}$ a set of $m$ knapsacks. Each object i of NS
is associated with a profit pi and a weight wi. Moreover, each pair of
objects i and j (1<= i =\=j <=n) generates a joint profit pij
when they are allocated to the same knapsack. Each knapsack k of M has
a weight capacity Ck. The quadratic multiple knapsack problem (QMKP) is
to assign objects of N to the knapsacks such that the total profit of
the allocated objects is maximized while the weight sum of the objects
allocated to each knapsack does not exceed the capacity of the knapsack.
Instance files
To come
Input file format
The format of the input data files is:
Output file format