Quadratic Knapsack Challenge Update

Aoibheann · January 7, 2025, 5:09pm

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:

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.
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].
Item weights w_i are drawn uniformly from the interval [1, 50].
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

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.
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.
**Weights:**Item weights remain uniformly drawn from [1, 50].
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:

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

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)

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.

github.com/tig-foundation/tig-monorepo

Enhanced Quadratic Knapsack Instance Generation

tig-foundation:blank_slate ← fatigue24:knapsack_update

opened 12:39AM - 03 Nov 24 UTC

fatigue24

+156 -28

# 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!

Pisinger, David. “The quadratic knapsack problem—a survey.” Discrete Applied Mathematics, vol. 155, no. 5, 2007, pp. 623–648. ↩︎
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. ↩︎
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. ↩︎
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. ↩︎ ↩︎
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] ↩︎ ↩︎
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. ↩︎
Gallo, Giorgio, et al. “Quadratic Knapsack Problems.” Combinatorial Optimization, Springer, 1980. ↩︎ ↩︎ ↩︎
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. ↩︎

syebastian · January 8, 2025, 1:47pm

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.

Topic		Replies	Views
Realigning Benchmark Incentives: Sub-Instance Averaging and New Difficulty Ranges Protocol Enhancements	0	28	April 25, 2025
Breakthrough Submission: Vehicle Routing Breakthrough Submission	7	432	January 20, 2025
Enhanced Block Reward Function Protocol Enhancements	3	196	March 21, 2025
Upcoming Challenge: Neural Network Gradient Descent Challenge Design	5	169	May 6, 2025
Vehicle Routing Challenge Update Challenge Design	4	183	April 1, 2025

Quadratic Knapsack Challenge Update

Quadratic Knapsack Challenge Update

Introduction

Motivation for Updates

Overview of Key Changes

Improved Instance Generation

Alignment with Academic Benchmarks

Comparison of Old vs New Generation

Future Considerations

Enhanced Baseline Algorithm

Performance Analysis

Runtime Efficiency

Solution Quality Improvement

Code

Related topics