This page contains the instances used for the computational experimental phase of the manuscript "Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem" by L. Galli, S. Martello, C. Rey, and P. Toth. (2021). European Journal of Operational Research, 291(3), 871-882.
The instances of this page were created using the free instance generator for the quadratic multiple knapsack problem in Bergman (2019). The format of the instances has the following scheme:
- Name of instance
Linear profits pi (i=1, …, n)
The next n-1 lines contain the pairwise profits pij (i=1, …, n-1; j=i+1, …,n)
The next line is empty
The next line contains a zero value (to be ignored)
The next line contains the capacity of the knapsack for the case m=1. For m >1, the (common) capacity is 0.8 W/m, where W is the sum of the item weights.
The last line contains the item weights wi (i=1, …, n)
D. Bergman. (2019). An exact algorithm for the quadratic multiknapsack problem with an application to event seating. INFORMS Journal on Computing, 31(3), 477-492.