Quadratic Multiple Knapsack Problem

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
  • n
  • 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.
 

Galli2021_instances.zip