solverforge_solver/heuristic/selector/k_opt/
nearby.rs

1// Nearby k-opt move selector for improved performance.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::k_opt_reconnection::{
10    enumerate_reconnections, KOptReconnection, THREE_OPT_RECONNECTIONS,
11};
12use crate::heuristic::r#move::{CutPoint, KOptMove};
13
14use super::super::entity::EntitySelector;
15use super::super::move_selector::{
16    CandidateId, CandidateStore, MoveCandidateRef, MoveCursor, MoveSelector,
17};
18use super::config::KOptConfig;
19use super::distance_meter::ListPositionDistanceMeter;
20
21/// A k-opt move selector with nearby selection for improved performance.
22///
23/// Instead of enumerating all O(n^k) cut combinations, uses distance-based
24/// pruning to reduce to O(n * m^(k-1)) where m = max_nearby_size.
25///
26/// # How It Works
27///
28/// 1. First cut: all positions in the route
29/// 2. Second cut: only positions nearby (by element distance) to first cut
30/// 3. Third cut: only positions nearby to second cut
31/// 4. etc.
32///
33/// This dramatically reduces the search space for large routes.
34pub struct NearbyKOptMoveSelector<S, V, D: ListPositionDistanceMeter<S>, ES> {
35    // Selects entities (routes) to apply k-opt to.
36    entity_selector: ES,
37    // Distance meter for nearby selection.
38    distance_meter: D,
39    // Maximum nearby positions to consider.
40    max_nearby: usize,
41    // K-opt configuration.
42    config: KOptConfig,
43    // Reconnection patterns.
44    patterns: Vec<&'static KOptReconnection>,
45    list_len: fn(&S, usize) -> usize,
46    list_get: fn(&S, usize, usize) -> Option<V>,
47    // Remove sublist.
48    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
49    // Insert sublist.
50    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
51    // Variable name.
52    variable_name: &'static str,
53    // Descriptor index.
54    descriptor_index: usize,
55    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
56}
57
58impl<S, V: Debug, D: ListPositionDistanceMeter<S>, ES: Debug> Debug
59    for NearbyKOptMoveSelector<S, V, D, ES>
60{
61    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
62        f.debug_struct("NearbyKOptMoveSelector")
63            .field("entity_selector", &self.entity_selector)
64            .field("max_nearby", &self.max_nearby)
65            .field("config", &self.config)
66            .field("pattern_count", &self.patterns.len())
67            .finish()
68    }
69}
70
71impl<S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
72    NearbyKOptMoveSelector<S, V, D, ES>
73{
74    #[allow(clippy::too_many_arguments)]
75    pub fn new(
76        entity_selector: ES,
77        distance_meter: D,
78        max_nearby: usize,
79        config: KOptConfig,
80        list_len: fn(&S, usize) -> usize,
81        list_get: fn(&S, usize, usize) -> Option<V>,
82        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
83        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
84        variable_name: &'static str,
85        descriptor_index: usize,
86    ) -> Self {
87        let patterns: Vec<&'static KOptReconnection> = if config.k == 3 {
88            THREE_OPT_RECONNECTIONS.iter().collect()
89        } else {
90            let generated = enumerate_reconnections(config.k);
91            let leaked: &'static [KOptReconnection] = Box::leak(generated.into_boxed_slice());
92            leaked.iter().collect()
93        };
94
95        Self {
96            entity_selector,
97            distance_meter,
98            max_nearby,
99            config,
100            patterns,
101            list_len,
102            list_get,
103            sublist_remove,
104            sublist_insert,
105            variable_name,
106            descriptor_index,
107            _phantom: PhantomData,
108        }
109    }
110}
111
112fn nearby_positions<S, D>(
113    solution: &S,
114    distance_meter: &D,
115    max_nearby: usize,
116    entity_idx: usize,
117    origin: usize,
118    len: usize,
119) -> Vec<usize>
120where
121    D: ListPositionDistanceMeter<S>,
122{
123    let mut positions: Vec<(usize, f64)> = (0..len)
124        .filter(|&p| p != origin)
125        .map(|p| {
126            let dist = distance_meter.distance(solution, entity_idx, origin, p);
127            (p, dist)
128        })
129        .collect();
130
131    positions.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
132    positions.truncate(max_nearby);
133    positions.into_iter().map(|(p, _)| p).collect()
134}
135
136impl<S, V, DM, ES> MoveSelector<S, KOptMove<S, V>> for NearbyKOptMoveSelector<S, V, DM, ES>
137where
138    S: PlanningSolution,
139    V: Clone + Send + Sync + Debug + 'static,
140    DM: ListPositionDistanceMeter<S> + 'static,
141    ES: EntitySelector<S>,
142{
143    type Cursor<'a>
144        = NearbyKOptMoveCursor<'a, S, V, DM>
145    where
146        Self: 'a;
147
148    fn open_cursor<'a, SD: Director<S>>(&'a self, score_director: &SD) -> Self::Cursor<'a> {
149        let solution = score_director.working_solution();
150        let entities = self
151            .entity_selector
152            .iter(score_director)
153            .map(|entity_ref| entity_ref.entity_index)
154            .collect();
155        NearbyKOptMoveCursor::new(
156            solution.clone(),
157            &self.distance_meter,
158            entities,
159            self.config.k,
160            self.config.min_segment_len,
161            self.max_nearby,
162            &self.patterns,
163            self.list_len,
164            self.list_get,
165            self.sublist_remove,
166            self.sublist_insert,
167            self.variable_name,
168            self.descriptor_index,
169        )
170    }
171
172    fn size<SD: Director<S>>(&self, score_director: &SD) -> usize {
173        // Approximate size: n * m^(k-1) * patterns
174        let k = self.config.k;
175        let m = self.max_nearby;
176        let pattern_count = self.patterns.len();
177
178        self.entity_selector
179            .iter(score_director)
180            .map(|entity_ref| {
181                let solution = score_director.working_solution();
182                let len = (self.list_len)(solution, entity_ref.entity_index);
183                if len < (k + 1) * self.config.min_segment_len {
184                    0
185                } else {
186                    // Approximate: first cut has ~len choices, others have ~m choices
187                    len.saturating_sub(k) * m.pow((k - 1) as u32) * pattern_count
188                }
189            })
190            .sum()
191    }
192}
193
194pub struct NearbyKOptMoveCursor<'a, S, V, D>
195where
196    S: PlanningSolution,
197    V: Clone + Send + Sync + Debug + 'static,
198    D: ListPositionDistanceMeter<S>,
199{
200    store: CandidateStore<S, KOptMove<S, V>>,
201    solution: S,
202    distance_meter: &'a D,
203    entities: Vec<usize>,
204    entity_offset: usize,
205    cut_state: Option<NearbyCutState>,
206    pending_cuts: Option<Vec<CutPoint>>,
207    pattern_offset: usize,
208    k: usize,
209    min_seg: usize,
210    max_nearby: usize,
211    patterns: &'a [&'static KOptReconnection],
212    list_len: fn(&S, usize) -> usize,
213    list_get: fn(&S, usize, usize) -> Option<V>,
214    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
215    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
216    variable_name: &'static str,
217    descriptor_index: usize,
218}
219
220impl<'a, S, V, D> NearbyKOptMoveCursor<'a, S, V, D>
221where
222    S: PlanningSolution,
223    V: Clone + Send + Sync + Debug + 'static,
224    D: ListPositionDistanceMeter<S>,
225{
226    #[allow(clippy::too_many_arguments)]
227    fn new(
228        solution: S,
229        distance_meter: &'a D,
230        entities: Vec<usize>,
231        k: usize,
232        min_seg: usize,
233        max_nearby: usize,
234        patterns: &'a [&'static KOptReconnection],
235        list_len: fn(&S, usize) -> usize,
236        list_get: fn(&S, usize, usize) -> Option<V>,
237        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
238        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
239        variable_name: &'static str,
240        descriptor_index: usize,
241    ) -> Self {
242        Self {
243            store: CandidateStore::new(),
244            solution,
245            distance_meter,
246            entities,
247            entity_offset: 0,
248            cut_state: None,
249            pending_cuts: None,
250            pattern_offset: 0,
251            k,
252            min_seg,
253            max_nearby,
254            patterns,
255            list_len,
256            list_get,
257            sublist_remove,
258            sublist_insert,
259            variable_name,
260            descriptor_index,
261        }
262    }
263
264    fn load_next_cut_state(&mut self) -> bool {
265        while self.entity_offset < self.entities.len() {
266            let entity_idx = self.entities[self.entity_offset];
267            self.entity_offset += 1;
268            let len = (self.list_len)(&self.solution, entity_idx);
269            let state = NearbyCutState::new(entity_idx, self.k, len, self.min_seg, self.max_nearby);
270            if !state.is_done() {
271                self.cut_state = Some(state);
272                return true;
273            }
274        }
275        false
276    }
277}
278
279impl<S, V, D> MoveCursor<S, KOptMove<S, V>> for NearbyKOptMoveCursor<'_, S, V, D>
280where
281    S: PlanningSolution,
282    V: Clone + Send + Sync + Debug + 'static,
283    D: ListPositionDistanceMeter<S>,
284{
285    fn next_candidate(&mut self) -> Option<CandidateId> {
286        loop {
287            if let Some(cuts) = self.pending_cuts.as_ref() {
288                if self.pattern_offset < self.patterns.len() {
289                    let pattern = self.patterns[self.pattern_offset];
290                    self.pattern_offset += 1;
291                    return Some(self.store.push(KOptMove::new(
292                        cuts,
293                        pattern,
294                        self.list_len,
295                        self.list_get,
296                        self.sublist_remove,
297                        self.sublist_insert,
298                        self.variable_name,
299                        self.descriptor_index,
300                    )));
301                }
302                self.pending_cuts = None;
303                self.pattern_offset = 0;
304            }
305
306            if self.cut_state.is_none() && !self.load_next_cut_state() {
307                return None;
308            }
309
310            if let Some(state) = self.cut_state.as_mut() {
311                if let Some(mut cuts) = state.next_cuts(&self.solution, self.distance_meter) {
312                    cuts.sort_by_key(|c| c.position());
313                    self.pending_cuts = Some(cuts);
314                    self.pattern_offset = 0;
315                    continue;
316                }
317            }
318            self.cut_state = None;
319        }
320    }
321
322    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, KOptMove<S, V>>> {
323        self.store.candidate(id)
324    }
325
326    fn take_candidate(&mut self, id: CandidateId) -> KOptMove<S, V> {
327        self.store.take_candidate(id)
328    }
329}
330
331impl<S, V, D> Iterator for NearbyKOptMoveCursor<'_, S, V, D>
332where
333    S: PlanningSolution,
334    V: Clone + Send + Sync + Debug + 'static,
335    D: ListPositionDistanceMeter<S>,
336{
337    type Item = KOptMove<S, V>;
338
339    fn next(&mut self) -> Option<Self::Item> {
340        let id = self.next_candidate()?;
341        Some(self.take_candidate(id))
342    }
343}
344
345// Iterator state for nearby k-cut combinations.
346struct NearbyCutState {
347    entity_idx: usize,
348    k: usize,
349    len: usize,
350    max_nearby: usize,
351    min_seg: usize,
352    // Stack of (position, nearby_iterator_index)
353    stack: Vec<(usize, usize)>,
354    // Nearby positions for each level
355    nearby_cache: Vec<Vec<usize>>,
356    done: bool,
357}
358
359impl NearbyCutState {
360    fn new(entity_idx: usize, k: usize, len: usize, min_seg: usize, max_nearby: usize) -> Self {
361        let min_len = (k + 1) * min_seg;
362        if len < min_len {
363            return Self {
364                entity_idx,
365                k,
366                len,
367                max_nearby,
368                min_seg,
369                stack: vec![],
370                nearby_cache: vec![],
371                done: true,
372            };
373        }
374
375        // Start with first valid position
376        Self {
377            entity_idx,
378            k,
379            len,
380            max_nearby,
381            min_seg,
382            stack: vec![(min_seg, 0)],
383            nearby_cache: vec![vec![]],
384            done: false,
385        }
386    }
387
388    fn is_done(&self) -> bool {
389        self.done
390    }
391
392    fn extend_stack<S, D>(&mut self, solution: &S, distance_meter: &D)
393    where
394        D: ListPositionDistanceMeter<S>,
395    {
396        while self.stack.len() < self.k && !self.done {
397            let (last_pos, _) = *self.stack.last().unwrap();
398
399            let nearby = nearby_positions(
400                solution,
401                distance_meter,
402                self.max_nearby,
403                self.entity_idx,
404                last_pos,
405                self.len,
406            );
407
408            // Filter to valid positions (must leave room for remaining cuts)
409            let remaining_cuts = self.k - self.stack.len();
410            let min_pos = last_pos + self.min_seg;
411            let max_pos = self.len - self.min_seg * remaining_cuts;
412
413            let valid: Vec<usize> = nearby
414                .into_iter()
415                .filter(|&p| p >= min_pos && p <= max_pos)
416                .collect();
417
418            if valid.is_empty() {
419                // No valid positions, backtrack
420                if !self.backtrack() {
421                    self.done = true;
422                    return;
423                }
424            } else {
425                self.nearby_cache.push(valid);
426                let next_pos = self.nearby_cache.last().unwrap()[0];
427                self.stack.push((next_pos, 0));
428            }
429        }
430    }
431
432    fn backtrack(&mut self) -> bool {
433        while let Some((popped_pos, _idx)) = self.stack.pop() {
434            self.nearby_cache.pop();
435
436            if let Some((_, last_idx)) = self.stack.last_mut() {
437                let cache_idx = self.nearby_cache.len();
438                if cache_idx > 0 {
439                    let cache = &self.nearby_cache[cache_idx - 1];
440                    let next_idx = *last_idx + 1;
441                    if next_idx < cache.len() {
442                        *last_idx = next_idx;
443                        let (pos, _) = self.stack.last().unwrap();
444                        let new_pos = cache[next_idx];
445                        if new_pos > *pos {
446                            self.stack.pop();
447                            self.stack.push((new_pos, next_idx));
448                            return true;
449                        }
450                    }
451                }
452            } else {
453                // Stack is empty - use the popped position to find next first position
454                let next_first = popped_pos + 1;
455                let max_first = self.len - self.min_seg * self.k;
456                if next_first <= max_first {
457                    self.stack.push((next_first, 0));
458                    self.nearby_cache.push(vec![]);
459                    return true;
460                }
461            }
462        }
463        false
464    }
465
466    fn advance<S, D>(&mut self, solution: &S, distance_meter: &D)
467    where
468        D: ListPositionDistanceMeter<S>,
469    {
470        if self.done || self.stack.is_empty() {
471            self.done = true;
472            return;
473        }
474
475        // Try to advance at current depth
476        if let Some((_, idx)) = self.stack.last_mut() {
477            let cache_idx = self.nearby_cache.len() - 1;
478            let cache = &self.nearby_cache[cache_idx];
479            let next_idx = *idx + 1;
480            if next_idx < cache.len() {
481                *idx = next_idx;
482                let new_pos = cache[next_idx];
483                self.stack.pop();
484                self.stack.push((new_pos, next_idx));
485                return;
486            }
487        }
488
489        // Backtrack and extend
490        if self.backtrack() {
491            self.extend_stack(solution, distance_meter);
492        } else {
493            self.done = true;
494        }
495    }
496
497    fn next_cuts<S, D>(&mut self, solution: &S, distance_meter: &D) -> Option<Vec<CutPoint>>
498    where
499        D: ListPositionDistanceMeter<S>,
500    {
501        self.extend_stack(solution, distance_meter);
502        if self.done || self.stack.len() != self.k {
503            return None;
504        }
505
506        let cuts: Vec<CutPoint> = self
507            .stack
508            .iter()
509            .map(|(pos, _)| CutPoint::new(self.entity_idx, *pos))
510            .collect();
511
512        self.advance(solution, distance_meter);
513
514        Some(cuts)
515    }
516}
solverforge_solver/heuristic/selector/k_opt/nearby.rs

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
