# Quadratic Knapsack Challenge Update

**URL:** <https://forum.tig.foundation/t/quadratic-knapsack-challenge-update/27>\
**Category:** Challenge Design\
**Created:** [January 7, 2025, 5:09pm UTC](https://forum.tig.foundation/t/quadratic-knapsack-challenge-update/27 "2025-01-07T17:09:58Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Aoibheann](https://avatars.discourse-cdn.com/v4/letter/a/bbce88/32.png) [@Aoibheann](https://forum.tig.foundation/u/Aoibheann)\
**Post date:** [January 7, 2025, 5:09pm UTC](https://forum.tig.foundation/t/quadratic-knapsack-challenge-update/27/1 "2025-01-07T17:09:59Z")

</div>

# Quadratic Knapsack Challenge Update

* * *

## Introduction

Welcome to our newest proposal - an update to the Quadratic Knapsack Challenge (QKC). This update, proposed by a dedicated member of our community, aims to align the challenge with established academic benchmarks and ensure that innovators have access to both realistic test instances and a stronger baseline solver. After reviewing and comparing this contribution against established academic literature, we are confident in the improvements this update would bring. However, before we move forward with this update, we would greatly appreciate your input.

We invite you to examine the following proposed changes and share your thoughts. Collaboration from the community is crucial for ensuring that the challenge remains relevant, fair, and scientifically robust.

* * *

## Motivation for Updates

We aim to ensure that our challenges remain aligned with established academic benchmarks. By doing so, we strengthen the scientific and technological relevance of the innovations incentivised by TIG. In the context of the Knapsack challenge, the efficient generation of instances that closely mirror real-world problem structures is crucial for encouraging practical, high-value contributions.

In line with our goal, the proposed changes aim to align QKC instance generation with classical literature while improving the baseline solver to set a higher standard for innovation. By doing so, the challenge can continue to inspire innovative solutions that are both conceptually rigorous and useful in real-world contexts.

* * *

## Overview of Key Changes

### Improved Instance Generation

#### Alignment with Academic Benchmarks

The most classical instance generation procedure, adopted by many authors \[1\] \[2\] \[3\] \[4\] \[5\] \[6\], originates from Gallo et al. \[7\]. Key steps include:

1. Linear and quadratic profits, p\_i and p\_{ij} (= p\_{ji}), are nonzero with a density d. When nonzero, they are drawn uniformly at random from the interval [1, 100], and are set to zero otherwise.
2. Four density values are commonly considered in the literature: d = 0.25, 0.50, 0.75, 1.00. In this update, density is fixed at d = 0.25 as lower-density instances have been noted to be more challenging and have become an area of interest in some recent academic studies \[5:1\], \[8\].
3. Item weights w\_i are drawn uniformly from the interval [1, 50].
4. Capacity C is chosen randomly from the interval [50,\sum\_{i=1}^n w\_i]. In this update, capacity is unchanged as C \;=\; \frac{1}{2}\sum\_{i=1}^n w\_i.

#### Comparison of Old vs New Generation

1. **Value Ranges:** Previously, linear coefficients were in [1, 50] and quadratic coefficients in [-50, 50]. Now, [1, 100] is used for both linear and quadratic coefficients. This modification adheres to the standard benchmarks proposed by Gallo et al.\[7:1\] and widely adopted in subsequent literature.
2. **Controlled Sparsity (Density):** This update employs a density parameter of 25%. Each linear or quadratic coefficient has a 25% probability of being nonzero. This sparse structure, in contrast to the previous fully dense matrices, more accurately models realistic scenarios where only a subset of interactions are significant.
3. \*\*Weights:\*\*Item weights remain uniformly drawn from [1, 50].
4. **Capacity:** The knapsack capacity remains fixed at  
 C \;=\; \frac{1}{2}\sum\_{i=1}^n w\_i.

#### Future Considerations

Schauer\[4:1\] criticised the use of randomly generated instances, such as those based on Gallo et. al.\[7:2\], commonly employed for computational experiments on algorithms for the QKP. He demonstrated that these instances often allow basic greedy-like algorithms to produce solutions whose value asymptotically approaches the optimum as the instance size grows indefinitely. In his work, Schauer introduced an additional class of instances, known as hidden-clique instances, which are significantly harder to solve. Should dominance of greedy-like algorithms be observed in TIG, we may propose a future update, adopting a similar methodology to increase instance complexity.

* * *

### Enhanced Baseline Algorithm

The baseline solution now consists of two stages:

1. **Greedy Selection:** Items are sorted by the ratio of total value (sum of its linear and interaction terms) to weight, and selected until the capacity is reached.
2. **Local Search with Tabu List:** A short-term tabu search mechanism (with a memory size of 3 iterations) is employed to iteratively improve the initial solution.
  - **Precomputing Interaction Values:** For each item, the sum of its interactions with already selected items is precomputed - marginal contributions are quickly evaluated.
  - **Tabu Swaps:** Items are swapped if value improves, with swaps temporarily restricted to avoid reversals.
  - **Early Termination:** If a potential new item’s contribution is below the smallest contribution among the currently selected items, the swap step is skipped - skips unpromising moves for faster convergence.

This two-stage method enhances the baseline solution’s quality relative to the older, single-stage greedy approach.

* * *

## Performance Analysis

### Runtime Efficiency

The new method demonstrates slightly slower performance compared to the pure greedy algorithm but remains efficient. For example, requiring approximately 20 seconds to generate 1,000 instances with 2000 items.

 ![qkp_runtime_1000](https://europe1.discourse-cdn.com/flex018/uploads/tig/original/1X/22451a1b1b8a6ea931128145200e43858cea9a00.png)

### Solution Quality Improvement

The new method achieves improvements in solution quality compared to the previous baseline approach. The formula for average baseline improvement is similar to the better\_than\_baseline computation and is defined as:

\text{average baseline improvement} = \left( \frac{\text{new\_min\_value - old\_min\_value}}{\text{old\_min\_value}} \times 1000 \right)

 ![Solution Quality Improvement vs Number of Items2](https://europe1.discourse-cdn.com/flex018/uploads/tig/original/1X/6d84eaf80d653b03a75655470a24f0352af52ed0.png)

The updated method consistently outperforms the previous baseline across varying instance sizes.

## Code

Below is the link to the proposed Rust implementation showcasing the revised instance generation and updated two-stage baseline solver. As this update is backward compatible, existing algorithms will still run if it is implemented, albeit with potentially poorer performance.

> <https://github.com/tig-foundation/tig-monorepo/pull/25>
>
> \# Enhanced Quadratic Knapsack Instance Generation
> 
> \## Changes
> \- Implemented a… two-step approach for generating better baseline solutions:
> 1. Initial greedy selection based on value-weight ratios
> 2. Local search optimization with tabu list to improve initial solution
> 
> \- Instance generation is aligned with generation method of academic benchmarks such as StandardQKP:
> 1. Weights remain in the range \[1, 50\].
> 2. Values range changed from \[1,50\] for linear coefficients and \[-50,50\] for quadratic coefficients to \[1,100\] for both linear and quadratic coefficients.
> 3. Added density variable which refers to probability of value to be non-zero and equal to 25%.
> 
> \- Key insights:
> - Added interaction value precomputation for faster evaluation
> - Introduced tabu search with a short-term memory (3 iterations)
> - Optimized swap operations by precomputing interaction sums
> - Added early termination for unpromising swaps(contribution of a new item is less than the minimum contribution among selected items).
> 
> \## Test Results
> \- Performance changes:
> - New method: 3.7s for 5000 instances
> - Old method: 3.17s for 5000 instances
> - ~16% slower execution time
> 
> \- Solution quality improvement:
> - formula similar to better\_than\_baseline computation( (new\_min\_value - old\_min\_value)/old\_min\_value \* 1000):
> - num\_items: 400:
> \`\`\`
> Average improvement: 5.63
> Range: 0.22 to 14.79
> \`\`\`
> - num\_items: 100:
> \`\`\`
> Average improvement: 17.54
> Range: 0.00 to 72.41
> \`\`\`
> The changes provide better quality baseline solutions and align instance generation with generation method of academic benchmarks. This results in more challenging but still feasible problem instances.
> 
> \<details\>
> \<summary\>Test Code(old method aligned with new variables ranges)\</summary\>
> 
> \`\`\`rust
> \#\[cfg(test)\]
> mod tests {
> use super::\*;
> use rand::{rngs::StdRng, Rng, SeedableRng, rngs::SmallRng};
> use std::time::{Instant, Duration};
> use tig\_challenges::ChallengeTrait;
> 
> fn generate\_instance\_old(seed: \[u8; 32\], difficulty: &tig\_challenges::knapsack::Difficulty) -\> anyhow::Result\<tig\_challenges::knapsack::Challenge, anyhow::Error\> {
> let mut rng = SmallRng::from\_seed(StdRng::from\_seed(seed).gen());
>     
> // Set constant density for value generation
> let density = 0.25;
> 
> // Generate weights w\_i in the range \[1, 50\]
> let weights: Vec\<u32\> = (0..difficulty.num\_items)
> .map(|\_| rng.gen\_range(1..=50))
> .collect();
> 
> // Generate values v\_i in the range \[1, 100\] with density probability, 0 otherwise
> let values: Vec\<u32\> = (0..difficulty.num\_items)
> .map(|\_| {
> if rng.gen\_bool(density) {
> rng.gen\_range(1..=100)
> } else {
> 0
> }
> })
> .collect();
> 
> // Generate interaction values V\_ij with the following properties:
> // - V\_ij == V\_ji (symmetric matrix)
> // - V\_ii == 0 (diagonal is zero)
> // - Values are in range \[1, 100\] with density probability, 0 otherwise
> let mut interaction\_values: Vec\<Vec\<i32\>\> = vec!\[vec!\[0; difficulty.num\_items\]; difficulty.num\_items\];
>         
> for i in 0..difficulty.num\_items {
> for j in (i + 1)..difficulty.num\_items {
> let value = if rng.gen\_bool(density) {
> rng.gen\_range(1..=100)
> } else {
> 0
> };
>                 
> // Set both V\_ij and V\_ji due to symmetry
> interaction\_values\[i\]\[j\] = value;
> interaction\_values\[j\]\[i\] = value;
> }
> }
>     
> let max\_weight: u32 = weights.iter().sum::\<u32\>() / 2;
>     
> // Precompute the ratio between the total value (value + sum of interactive values) and
> // weight for each item. Pair the ratio with the item's weight and index
> let mut value\_weight\_ratios: Vec\<(usize, f32, u32)\> = (0..difficulty.num\_items)
> .map(|i| {
> let total\_value = values\[i\] as i32 + interaction\_values\[i\].iter().sum::\<i32\>();
> let weight = weights\[i\];
> let ratio = total\_value as f32 / weight as f32;
> (i, ratio, weight)
> })
> .collect();
>     
> // Sort the list of tuples by value-to-weight ratio in descending order
> value\_weight\_ratios.sort\_unstable\_by(|&(\_, ratio\_a, \_), &(\_, ratio\_b, \_)| {
> ratio\_b.partial\_cmp(&ratio\_a).unwrap()
> });
>     
> let mut total\_weight = 0;
> let mut selected\_indices = Vec::new();
> for &(i, \_, weight) in &value\_weight\_ratios {
> if total\_weight + weight \<= max\_weight {
> selected\_indices.push(i);
> total\_weight += weight;
> }
> }
> selected\_indices.sort\_unstable();
>     
> let mut min\_value = tig\_challenges::knapsack::calculate\_total\_value(&selected\_indices, &values, &interaction\_values);
> min\_value = (min\_value as f32 \* (1.0 + difficulty.better\_than\_baseline as f32 / 1000.0))
> .round() as u32;
>     
> Ok(tig\_challenges::knapsack::Challenge {
> seed,
> difficulty: difficulty.clone(),
> weights,
> values,
> interaction\_values,
> max\_weight,
> min\_value,
> })
> }
> #\[test\]
> fn benchmark\_old\_generation() {
> let difficulty = tig\_challenges::knapsack::Difficulty {
> num\_items: 400,
> better\_than\_baseline: 0,
> };
>     
> let num\_instances = 5000;
> let rng\_seed: \[u8; 32\] = \[42; 32\]; 
> let mut rng = StdRng::from\_seed(rng\_seed);
>     
> let seeds: Vec\<\[u8; 32\]\> = (0..num\_instances)
> .map(|\_| std::array::from\_fn(|\_| rng.gen::\<u8\>()))
> .collect();
>     
> // Warmup
> let warmup\_sum: u32 = seeds.iter().take(1000)
> .map(|seed| generate\_instance\_old(\*seed, &difficulty).unwrap().min\_value)
> .sum();
> println!("Warmup sum: {}", warmup\_sum);
>     
> // Benchmark
> let start = Instant::now();
> let sum: u32 = seeds.iter()
> .map(|seed| generate\_instance\_old(\*seed, &difficulty).unwrap().min\_value)
> .sum();
> let elapsed = start.elapsed();
> println!("Old method time: {:?}", elapsed);
> println!("Sum: {}", sum);
> }
>     
> #\[test\]
> fn benchmark\_new\_generation() {
> let difficulty = tig\_challenges::knapsack::Difficulty {
> num\_items: 400,
> better\_than\_baseline: 0,
> };
>     
> let num\_instances = 5000;
> let rng\_seed: \[u8; 32\] = \[42; 32\]; 
> let mut rng = StdRng::from\_seed(rng\_seed);
>     
> let seeds: Vec\<\[u8; 32\]\> = (0..num\_instances)
> .map(|\_| std::array::from\_fn(|\_| rng.gen::\<u8\>()))
> .collect();
>     
> // Warmup
> let warmup\_sum: u32 = seeds.iter().take(1000)
> .map(|seed| tig\_challenges::knapsack::Challenge::generate\_instance(\*seed, &difficulty).unwrap().min\_value)
> .sum();
> println!("Warmup sum: {}", warmup\_sum);
>     
> // Benchmark
> let start = Instant::now();
> let sum: u32 = seeds.iter()
> .map(|seed| tig\_challenges::knapsack::Challenge::generate\_instance(\*seed, &difficulty).unwrap().min\_value)
> .sum();
> let elapsed = start.elapsed();
> println!("New method time: {:?}", elapsed);
> println!("Sum: {}", sum);
> }
>     
> #\[test\]
> fn compare\_solutions() {
> let difficulty = tig\_challenges::knapsack::Difficulty {
> num\_items: 400,
> better\_than\_baseline: 0,
> };
>     
> let num\_instances = 5000;
> let rng\_seed: \[u8; 32\] = \[42; 32\]; 
> let mut rng = StdRng::from\_seed(rng\_seed);
>     
> let seeds: Vec\<\[u8; 32\]\> = (0..num\_instances)
> .map(|\_| std::array::from\_fn(|\_| rng.gen::\<u8\>()))
> .collect();
>     
> let old\_values: Vec\<\_\> = seeds.iter()
> .map(|seed| generate\_instance\_old(\*seed, &difficulty).unwrap().min\_value)
> .collect();
>     
> let new\_values: Vec\<\_\> = seeds.iter()
> .map(|seed| tig\_challenges::knapsack::Challenge::generate\_instance(\*seed, &difficulty).unwrap().min\_value)
> .collect();
>     
> let improvements: Vec\<f64\> = old\_values.iter().zip(new\_values.iter())
> .map(|(old, new)| ((new - old) as f64 / \*old as f64) \* 1000.0)
> .collect();
>     
> let min\_improvement = improvements.iter().copied().fold(f64::INFINITY, f64::min);
> let max\_improvement = improvements.iter().copied().fold(f64::NEG\_INFINITY, f64::max);
> let avg\_improvement = improvements.iter().sum::\<f64\>() / improvements.len() as f64;
>     
> println!("\\nSolution quality metrics:");
> println!(" Average improvement: {:.2}", avg\_improvement);
> println!(" Range: {:.2} to {:.2}", min\_improvement, max\_improvement);
> }
> }
> \`\`\`
> \</details\>

We encourage you to scrutinise this code and post any feedback in this thread.

* * *

Huge thanks to the community member who brought us this update! We look forward to your feedback and hope to finalise this community-driven improvement to push next round. Thank you for your continued support and engagement!

* * *

* * *

1. Pisinger, David. “The quadratic knapsack problem—a survey.” _Discrete Applied Mathematics_, vol. 155, no. 5, 2007, pp. 623–648. 

2. Fomeni, Franklin Djeumou, Kaparis, Konstantinos, and Letchford, Adam N. “A cut-and-branch algorithm for the quadratic knapsack problem.” _Discrete Optimization_, vol. 44, p. 100579, 2022. 

3. Fennich, ME, Coelho, LC, and Fomeni, F. Djeumou. “Tight upper and lower bounds for the quadratic knapsack problem through binary decision diagram.” _Les Cahiers du GERAD ISSN_, vol. 711, pp. 2440, 2024. 

4. Schauer, Joachim. “Asymptotic behavior of the quadratic knapsack problem.” _European Journal of Operational Research_, vol. 255, no. 2, 2016, pp. 357–363. doi: [10.1016/j.ejor.2016.06.013](https://doi.org/10.1016/j.ejor.2016.06.013). 

5. Hochbaum, D.S., Baumann, P., Goldschmidt, O., and Zhang, Y. “A fast and effective breakpoints heuristic algorithm for the quadratic Knapsack problem.” _European Journal of Operational Research_, 2024. doi: [10.1016/j.ejor.2024.12.019] 

6. Galli, Laura, Martello, Silvano, and Toth, Paolo. “The quadratic knapsack problem.” _European Journal of Operational Research_, 2024. doi: [10.1016/j.ejor.2024.12.032](https://doi.org/10.1016/j.ejor.2024.12.032). 

7. Gallo, Giorgio, et al. “Quadratic Knapsack Problems.” _Combinatorial Optimization_, Springer, 1980. 

8. Pisinger, W. David, Rasmussen, Anders Bo, and Sandvik, Rune. “Solution of large quadratic knapsack problems through aggressive reduction.” _INFORMS Journal on Computing_, vol. 19, no. 2, 2007, pp. 280–290.

---

<div class="post-metadata">

**Author:** ![syebastian](https://avatars.discourse-cdn.com/v4/letter/s/d26b3c/32.png) [@syebastian](https://forum.tig.foundation/u/syebastian)\
**Post date:** [January 8, 2025, 1:47pm UTC](https://forum.tig.foundation/t/quadratic-knapsack-challenge-update/27/2 "2025-01-08T13:47:38Z")

</div>

> [@Aoibheann](#):
>
> Schauer[[4:1]](#footnote-28-4) criticised the use of randomly generated instances, such as those based on Gallo et. al.[[7:2]](#footnote-28-7), commonly employed for computational experiments on algorithms for the QKP. He demonstrated that these instances often allow basic greedy-like algorithms to produce solutions whose value asymptotically approaches the optimum as the instance size grows indefinitely.

So, according to Schauer’s research, the most challenging are randomly generated instances with a small number of items, and a reasonable argument is to lower the minimum number of elements from 1000 to 100, which is the smallest number of items in the Gallo benchmarks.  
The second point is that we must ensure that solvers work well with any number of items, and it makes sense not to limit the range of benchmarking to a large number of items.