Our Knapsack Challenge Evaluator provides a streamlined framework for benchmarking TIG Knapsack algorithms against state-of-the-art (SOTA) methods on key academic datasets.
The goal of this thread is to encourage community involvement in shaping our evaluation framework. We invite you to contribute by engaging with this post – read our rationale for the current approach, share your feedback, suggest new benchmark datasets, propose additional comparison metrics, or recommend new SOTA algorithms to include.
The remainder of this post explains the rationale behind our current selection of datasets, benchmark SOTA algorithms, and comparison metrics, and outlines the features we are planning to add in future updates.
Datasets
The evaluation suite uses several benchmark datasets for the Quadratic Knapsack Problem (QKP). All instances and their corresponding optimal (or best-known) objective function values (OFV) are sourced from benchmark-instances-for-qkp and results-for-qkp-benchmark-instances.
These instances are Standard QKP instances, generated based on the procedure proposed by Gallo et al. [1], which has been a standard in the QKP literature for decades (e.g., Caprara et al., 1999[2]; Pisinger et al., 2007[3]; Chen and Hao, 2017[4]). The generation process follows these key steps:
- Linear (p_i) and quadratic profits (p_{ij}=p_{ji}) are non-zero with a given density, d. Non-zero values are drawn uniformly from [1,100].
- The graph density d is varied across d\in\{0.25,0.5,0.75,1.0\}.
- Item weights w_i are drawn uniformly from [1,50].
- The knapsack capacity C is selected randomly from the interval [50,\sum_{i=1}^nw_i].
The knapsack evaluator currently supports the following collections:
- Standard QKP: 100 classic instances widely used in the literature, with sizes ranging from 100 to 300 items.
- QKP Group II: 80 larger instances with 1,000 to 2,000 items.
- QKP Group III: 40 large-scale instances with 5,000 to 6,000 items.
- Large QKP: A newer set of 144 instances with sizes from 500 to 10,000 items. Unlike the others, each graph in this collection has multiple capacity constraints, defined as a fraction γ of the total item weight: C=⌊γ\sum_{j=1}^nw_j⌋, where γ\in\{0.025,0.05,0.1,0.25,0.5,0.75\}.
SOTA Benchmark Methods
Rationale for Selected Methods
To provide a relevant and rigorous comparison, we benchmark TIG algorithms against a set of SOTA methods featured in the recent computational study by Hochbaum et al. (2025)[5].
The primary algorithm for comparison, QKBP, was chosen because its design philosophy aligns with the TIG ecosystem: it prioritizes achieving high-quality solutions with exceptional speed. The authors note that QKBP “consistently delivers high quality solutions regardless of instance size, density, or budget… in significantly faster running times than all leading algorithms.” This focus on both speed and quality makes it an excellent benchmark for our purposes. The other algorithms are included to provide the same comprehensive context as the original paper.
The following table details the SOTA comparison algorithms:
| Name | Abbreviation | Reference |
|---|---|---|
| Breakpoints Algorithm | QKBP | Hochbaum et al. (2025) |
| Relative Greedy Heuristic | RG | Julstrom (2005) |
| Iterated Hyperplane Exploration Approach | IHEA | Chen and Hao (2017) |
| Gurobi-based Approach | Gurobi | www.gurobi.com |
| Hexaly-based Approach | Hexaly | www.hexaly.com |
Key Benchmarks
- IHEA: A highly effective algorithm that consistently finds near-optimal solutions. However, this accuracy comes at a significant computational cost, running approximately 100x slower than QKBP.
- QKBP (2025): A recently published, peer-reviewed algorithm that produces high-quality solutions with significantly faster runtimes than previous SOTA methods.
The current top-performing TIG algorithm demonstrates superior solution quality compared to QKBP across a wide range of benchmark instances while operating at a similarly fast runtime. Therefore, comparison against this SOTA algorithm provides the most direct and fair “apples-to-apples” comparison.
Comparison Metrics
We evaluate algorithm performance using the Relative Percentage Deviation (RPD) from the best known Objective Function Value (OFV), in this case the OFV is the knapsack value. RPD is a standard metric in the QKP literature [4:1][5:1] for comparing solution quality. It is calculated as:
The primary visualization in the evaluator is a graph tracking the average RPD of the top-earning TIG algorithms by round against the SOTA algorithms for each benchmark dataset.
Future Work
We are continually enhancing the evaluation suite, with several key improvements on the horizon.
To strengthen our comparison benchmarks, we plan to include more challenging and structurally diverse datasets. As Schauer (2016)[6] highlights, the standard Gallo et al.[1:1] procedure can sometimes yield instances that are relatively easy for simple greedy heuristics, particularly as instance size grows. To address this, we will add support for instance types that avoid this property, including:
Runtime is a critical performance factor in QKP research. We aim to introduce precise runtime comparisons to quantify the computational speed-up and efficiency of TIG algorithms relative to SOTA methods. For example, while QKBP (2025)[5:2] delivers slightly lower solution quality than IHEA (2017)[4:2], it achieves results in a fraction of the time, reflecting a deliberate trade-off between quality and speed. Accurately capturing this balance is essential for fair evaluation.
Finally, we plan to add richer performance visualizations to help innovators more effectively create, test, and compare algorithmic behavior.
Giorgio Gallo, Peter L. Hammer, and Bruno Simeone. “Quadratic knapsack problems”. In: Combinatorial Optimization (1980), pp. 132–149. ↩︎ ↩︎
Caprara, A., Letchford, A.N., and Salazar-González, J.J. (1999). European Journal of Operational Research, 123(2), pp. 222–231. ↩︎
D. Pisinger, A.B. Rasmussen & R. Sandvik (2007). Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput., 19, pp.280–290. ↩︎ ↩︎ ↩︎
Chen, Y. and Hao, J.K., 2017. An iterated “hyperplane exploration” approach for the quadratic knapsack problem. Computers & Operations Research, 77, pp.226–239. ↩︎ ↩︎ ↩︎
Hochbaum, D.S., Baumann, P., Goldschmidt, O. and Zhang, Y., 2025. A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem. European Journal of Operational Research, 323(2), pp.425–440. ↩︎ ↩︎ ↩︎
J. Schauer (2016). Asymptotic behavior of the quadratic knapsack problem. Eur. J. Oper. Res., 255, pp.357–363. ↩︎ ↩︎