givp 1.0.0

GRASP-ILS-VND with Path Relinking metaheuristic for continuous black-box optimization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

// SPDX-FileCopyrightText: 2026 Arnaldo Mendes Pires Junior
// SPDX-License-Identifier: MIT

use std::collections::HashMap;

/// LRU evaluation cache to avoid redundant objective function calls.
pub(crate) struct EvaluationCache {
    maxsize: usize,
    cache: HashMap<u64, f64>,
    insertion_order: Vec<u64>,
    hits: usize,
    misses: usize,
}

impl EvaluationCache {
    pub fn new(maxsize: usize) -> Self {
        Self {
            maxsize,
            cache: HashMap::with_capacity(maxsize),
            insertion_order: Vec::with_capacity(maxsize),
            hits: 0,
            misses: 0,
        }
    }

    fn hash_solution(&self, solution: &[f64], half: usize) -> u64 {
        use std::hash::{Hash, Hasher};
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        for (i, &v) in solution.iter().enumerate() {
            let rounded = if i < half {
                (v * 1000.0).round() as i64
            } else {
                v.round() as i64
            };
            rounded.hash(&mut hasher);
        }
        hasher.finish()
    }

    pub fn get(&mut self, solution: &[f64], half: usize) -> Option<f64> {
        let key = self.hash_solution(solution, half);
        match self.cache.get(&key) {
            Some(&v) => {
                self.hits += 1;
                Some(v)
            }
            None => {
                self.misses += 1;
                None
            }
        }
    }

    pub fn put(&mut self, solution: &[f64], half: usize, cost: f64) {
        let key = self.hash_solution(solution, half);
        if self.cache.contains_key(&key) {
            return;
        }
        if self.cache.len() >= self.maxsize {
            // insertion_order is always in sync with cache (invariant maintained by put/clear)
            let oldest = self.insertion_order.remove(0);
            self.cache.remove(&oldest);
        }
        self.cache.insert(key, cost);
        self.insertion_order.push(key);
    }

    pub fn clear(&mut self) {
        self.cache.clear();
        self.insertion_order.clear();
    }

    #[allow(dead_code)]
    pub fn stats(&self) -> (usize, usize, f64, usize) {
        let total = self.hits + self.misses;
        let rate = if total > 0 {
            self.hits as f64 / total as f64
        } else {
            0.0
        };
        (self.hits, self.misses, rate, self.cache.len())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_cache_stats_empty() {
        let cache = EvaluationCache::new(10);
        let (hits, misses, rate, len) = cache.stats();
        assert_eq!(hits, 0);
        assert_eq!(misses, 0);
        assert_eq!(rate, 0.0);
        assert_eq!(len, 0);
    }

    #[test]
    fn test_cache_stats_after_use() {
        let mut cache = EvaluationCache::new(10);
        cache.get(&[1.0, 2.0], 2); // miss
        cache.put(&[1.0, 2.0], 2, 42.0);
        cache.get(&[1.0, 2.0], 2); // hit
        let (hits, misses, rate, len) = cache.stats();
        assert_eq!(hits, 1);
        assert_eq!(misses, 1);
        assert!((rate - 0.5).abs() < 1e-10);
        assert_eq!(len, 1);
    }

    #[test]
    fn test_cache_put_duplicate_key() {
        let mut cache = EvaluationCache::new(10);
        cache.put(&[1.0, 2.0], 2, 10.0);
        cache.put(&[1.0, 2.0], 2, 99.0); // same key — should be ignored (early return)
                                         // Value should still be 10.0
        assert_eq!(cache.get(&[1.0, 2.0], 2), Some(10.0));
        assert_eq!(cache.stats().3, 1); // only 1 entry
    }

    #[test]
    fn test_cache_lru_eviction() {
        let mut cache = EvaluationCache::new(2);
        cache.put(&[1.0], 1, 1.0);
        cache.put(&[2.0], 1, 2.0);
        cache.put(&[3.0], 1, 3.0); // evicts [1.0]
        assert_eq!(cache.get(&[1.0], 1), None);
        assert_eq!(cache.get(&[2.0], 1), Some(2.0));
        assert_eq!(cache.get(&[3.0], 1), Some(3.0));
    }

    #[test]
    fn test_cache_clear_removes_entries() {
        let mut cache = EvaluationCache::new(4);
        cache.put(&[1.0, 2.0], 2, 3.0);
        cache.put(&[2.0, 3.0], 2, 5.0);
        assert_eq!(cache.stats().3, 2);

        cache.clear();

        assert_eq!(cache.get(&[1.0, 2.0], 2), None);
        assert_eq!(cache.get(&[2.0, 3.0], 2), None);
        assert_eq!(cache.stats().3, 0);
    }
}