Knapsack Instances Update

Challenge Design
1

We are updating the Knapsack instance class from Standard QKP to Team Formation QKP. This post includes a detailed description of the Team Formation QKP instance class [1], which we will use across all knapsack tracks. The goal of this update is to introduce more realistic, real-world instances that will incentivise the development of algorithms with more practical industry relevance.

Team Formation

The Team Formation instances are derived from the team formation benchmark introduced by Hochbaum et al.[2] In the original team formation problem, the goal is to select a team of experts that maximizes collaboration utility while satisfying additional constraints on required skills.

The collaboration utility between two experts i and j is defined as the Jaccard similarity:

J(i,j) = \frac{|P_i \cap P_j|}{|P_i \cup P_j|},

where P_i denotes the set of projects on which expert i has worked.

The synthetic team formation instances are formed by assigning projects to experts using a lognormal distribution with mean 4 and standard deviation 1.

Each instance is defined by the number of experts n and number of projects p:

n \in \{1000, 2000, 4000, 6000, 8000, 10{,}000\},
p \in \{30000, 70000\}.

The project universe is first partitioned into subsets whose sizes are drawn sequentially from a lognormal distribution; the final subset contains any remaining projects. Each participant i is assigned a target number n_i of projects P_i, drawn independently from the same lognormal distribution.

Participant i then selects one subset uniformly at random. If the subset size is at least n_i, then n_i projects are sampled uniformly from it; otherwise, the entire subset is assigned and the remaining projects are drawn uniformly from the rest of the project universe.

Pairwise utilities are computed as Jaccard similarities:

p_{ij} = \frac{|P_i \cap P_j|}{|P_i \cup P_j|}, \quad \text{for } i < j,

with p_{ij} = p_{ji}. If two experts share no projects, then p_{ij} = 0.

In team formation instances, linear profits are 0, p_i=0 \text{ } \forall i.
This procedure yields a sparse, weighted, undirected graph whose edge weights capture collaboration strength derived from project co-membership.

A weight w_i is assigned to each expert i:

w_i \sim \mathrm{UD}[1,10].

The capacity of the knapsack is defined as a budget fraction of the total weight:

C = b \sum_{i=1}^n w_i \quad \text{where } b \in \{0.025, 0.05, 0.1, 0.25, 0.5, 0.75\}.

Tracks

The following tracks will form the initial setup:

n_items=1000, budget=5

n_items=1000, budget=10

n_items=1000, budget=25

n_items=5000, budget=10

n_items=5000, budget=25

  1. D.S. Hochbaum et al. A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem. European Journal of Operational Research (2024). ↩︎

  2. Dorit S. Hochbaum, Zhihao Liu, and Olivier Goldschmidt. A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems. SIAM Conference on Applied and Computational Discrete Algorithms. ↩︎