Problem Description

The quadratic multiple knapsack problem (QMKP) consists in assigning a set of objects, which interact through paired values, exclusively to different capacity-constrained knapsacks with the aim of maximising total profit. Its many applications include the assignment of workmen to different tasks when their ability to cooperate may affect the results.

Strategic oscillation (SO) is a search strategy that operates in relation to a critical boundary associated with important solution features (such as feasibility). Originally proposed in the context of tabu search, it has become widely applied as an efficient memory-based methodology. We apply strategic oscillation to the quadratic multiple knapsack problem, disclosing that SO effectively exploits domain-specific knowledge, and obtains solutions of particularly high quality compared to those obtained by current state-of-the-art algorithms.

Problem Instances

Billionnet and Soutif described exact algorithms for the quadratic (single-)knapsack problem and posted on-line a collection of randomly-generated QKP Instances. From twenty of these, Hiley and Julstrom constructed 60 QMKP instances with n = 100 and 200 objects and three to ten knapsacks. In particular, Billionnet and Soutif profide twenty QKP instances with denstiy 0.25, ten with 100 objects and ten with 200 objects. Hiley and Julstrom used the first five instances from each group, setting the number of knapsacks K to three, five, and ten, to generate 30 QMKP instances. Thirty more QMKP instances were generated in the same way from the posted QKP instances with density 0.75. For each QMKP instance, knapsack capacities are set to 80% of the sum of the instance's objects' weights divided by the number of knapsacks

Download QKP instances.

Results

The following zip file contains the results of our SO algorithm on the QMKP instances considered in this study. It contains 60 pairs of files with the following nomenclature "jeu____." where takes values from the set {100,200}; from {25, 75}, which represents the percentage of paired profit values; from {1,2,3,4,5}; from {3, 5, 10}; and from {'f', 'times'} according to whether the file contains objective function values or it contains timestamps of the search process, respectively. Each line in every file represents an execution of the algorithm in the corresponding problem instance, and the values in each line are paired, so the objective function value in the 'f' file is that of the best solution found by the algorithm at the corresponding timestamp in the 'times' file. resultsSO_QMKP.zip

The results of the TIG algorithm on the QMKP instances can be downloaded from Results of TIG

Additionally, the following spreadsheets provide the results of the algorithms ABC, TIG, and SO on the QMKP instances according to the specified running times (please, contact the corresponding author if you find any error): results.xls, results.ods