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

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