Implemented a two-step approach for generating better baseline solutions:
Initial greedy selection based on value-weight ratios
Local search optimization with tabu list to improve initial solution
Instance generation is aligned with generation method of academic benchmarks such as StandardQKP:
Weights remain in the range [1, 50].
Values range changed from [1,50] for linear coefficients and [-50,50] for quadratic coefficients to [1,100] for both linear and quadratic coefficients.
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.
Test Code(old method aligned with new variables ranges)
```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 {
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 = (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 = (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![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::() / 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::();
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::()))
.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::()))
.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::()))
.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 = 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::() / improvements.len() as f64;
println!("\nSolution quality metrics:");
println!(" Average improvement: {:.2}", avg_improvement);
println!(" Range: {:.2} to {:.2}", min_improvement, max_improvement);
}
}
```
Enhanced Quadratic Knapsack Instance Generation
Changes
Implemented a two-step approach for generating better baseline solutions:
Instance generation is aligned with generation method of academic benchmarks such as StandardQKP:
Key insights:
Test Results
Performance changes:
Solution quality improvement:
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.
Test Code(old method aligned with new variables ranges)
```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