solverforge_solver/heuristic/selector/
list_ruin.rs

1/* List ruin move selector for Large Neighborhood Search on list variables.
2
3Generates `ListRuinMove` instances that remove elements from list variables,
4enabling exploration of distant regions in the solution space.
5
6# Zero-Erasure Design
7
8Uses `fn` pointers for list operations. No `Arc<dyn Fn>`, no trait objects
9in hot paths.
10
11# Example
12
13```
14use solverforge_solver::heuristic::selector::{MoveSelector, ListRuinMoveSelector};
15use solverforge_solver::heuristic::r#move::ListRuinMove;
16use solverforge_core::domain::PlanningSolution;
17use solverforge_core::score::SoftScore;
18use solverforge_scoring::{Director, ScoreDirector};
19use solverforge_core::domain::SolutionDescriptor;
20use std::any::TypeId;
21
22#[derive(Clone, Debug)]
23struct Route { stops: Vec<i32> }
24
25#[derive(Clone, Debug)]
26struct VrpSolution { routes: Vec<Route>, score: Option<SoftScore> }
27
28impl PlanningSolution for VrpSolution {
29type Score = SoftScore;
30fn score(&self) -> Option<Self::Score> { self.score }
31fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
32}
33
34fn entity_count(s: &VrpSolution) -> usize { s.routes.len() }
35fn list_len(s: &VrpSolution, idx: usize) -> usize {
36s.routes.get(idx).map_or(0, |r| r.stops.len())
37}
38fn list_remove(s: &mut VrpSolution, entity_idx: usize, idx: usize) -> i32 {
39s.routes.get_mut(entity_idx).map(|r| r.stops.remove(idx)).unwrap_or(0)
40}
41fn list_insert(s: &mut VrpSolution, entity_idx: usize, idx: usize, v: i32) {
42if let Some(r) = s.routes.get_mut(entity_idx) { r.stops.insert(idx, v); }
43}
44
45// Create selector that removes 2-3 elements at a time
46let selector = ListRuinMoveSelector::<VrpSolution, i32>::new(
472, 3,
48entity_count,
49list_len, list_remove, list_insert,
50"stops", 0,
51);
52
53// Use with a score director
54let solution = VrpSolution {
55routes: vec![Route { stops: vec![1, 2, 3, 4, 5] }],
56score: None,
57};
58let descriptor = SolutionDescriptor::new("VrpSolution", TypeId::of::<VrpSolution>());
59let director = ScoreDirector::simple(
60solution, descriptor, |s, _| s.routes.len()
61);
62
63let moves: Vec<_> = selector.iter_moves(&director).collect();
64assert!(!moves.is_empty());
65```
66*/
67
68use std::cell::RefCell;
69use std::fmt::Debug;
70use std::marker::PhantomData;
71
72use rand::rngs::SmallRng;
73use rand::{RngExt, SeedableRng};
74use smallvec::SmallVec;
75use solverforge_core::domain::PlanningSolution;
76use solverforge_scoring::Director;
77
78use crate::heuristic::r#move::ListRuinMove;
79
80use super::move_selector::{
81    CandidateId, CandidateStore, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
82};
83
84/// A move selector that generates `ListRuinMove` instances for Large Neighborhood Search.
85///
86/// Selects random subsets of elements from list variables to "ruin" (remove),
87/// enabling a construction heuristic to reinsert them in better positions.
88///
89/// # Type Parameters
90/// * `S` - The planning solution type
91/// * `V` - The list element value type
92///
93/// # Zero-Erasure
94///
95/// All list access uses `fn` pointers:
96/// - `list_len: fn(&S, usize) -> usize` - gets list length
97/// - `list_remove: fn(&mut S, usize, usize) -> V` - removes element
98/// - `list_insert: fn(&mut S, usize, usize, V)` - inserts element
99/// - `entity_count: fn(&S) -> usize` - counts entities
100pub struct ListRuinMoveSelector<S, V> {
101    // Minimum elements to remove per move.
102    min_ruin_count: usize,
103    // Maximum elements to remove per move.
104    max_ruin_count: usize,
105    // RNG state for reproducible subset selection.
106    rng: RefCell<SmallRng>,
107    // Function to get entity count from solution.
108    entity_count: fn(&S) -> usize,
109    // Function to get list length for an entity.
110    list_len: fn(&S, usize) -> usize,
111    // Function to read a list element by position for move metadata.
112    list_get: fn(&S, usize, usize) -> Option<V>,
113    // Function to remove element at index, returning it.
114    list_remove: fn(&mut S, usize, usize) -> V,
115    // Function to insert element at index.
116    list_insert: fn(&mut S, usize, usize, V),
117    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
118    precedence_element_count: Option<fn(&S) -> usize>,
119    precedence_index_to_element: Option<fn(&S, usize) -> V>,
120    precedence_successors_fn: Option<fn(&S, V, &mut Vec<V>)>,
121    // Variable name.
122    variable_name: &'static str,
123    // Entity descriptor index.
124    descriptor_index: usize,
125    // Number of ruin moves to generate per iteration.
126    moves_per_step: usize,
127    // Optional cap on source list length for specialized route-emptying selectors.
128    max_source_list_len: Option<usize>,
129    // Optional recreate pruning for domains where opening empty lists is undesirable.
130    skip_empty_destinations: bool,
131    _phantom: PhantomData<fn() -> V>,
132}
133
134// SAFETY: RefCell<SmallRng> is accessed only while opening a cursor to derive
135// that cursor's private seed. Each cursor owns its SmallRng and is consumed from
136// a single thread at a time.
137unsafe impl<S, V> Send for ListRuinMoveSelector<S, V> {}
138
139impl<S, V: Debug> Debug for ListRuinMoveSelector<S, V> {
140    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
141        f.debug_struct("ListRuinMoveSelector")
142            .field("min_ruin_count", &self.min_ruin_count)
143            .field("max_ruin_count", &self.max_ruin_count)
144            .field("moves_per_step", &self.moves_per_step)
145            .field("max_source_list_len", &self.max_source_list_len)
146            .field("skip_empty_destinations", &self.skip_empty_destinations)
147            .field(
148                "has_precedence_recreate_filter",
149                &self.precedence_successors_fn.is_some(),
150            )
151            .field("variable_name", &self.variable_name)
152            .field("descriptor_index", &self.descriptor_index)
153            .finish()
154    }
155}
156
157impl<S, V> ListRuinMoveSelector<S, V> {
158    /* Creates a new list ruin move selector with concrete function pointers.
159
160    # Arguments
161    * `min_ruin_count` - Minimum elements to remove (at least 1)
162    * `max_ruin_count` - Maximum elements to remove
163    * `entity_count` - Function to get total entity count
164    * `list_len` - Function to get list length for an entity
165    * `list_remove` - Function to remove element at index
166    * `list_insert` - Function to insert element at index
167    * `variable_name` - Name of the list variable
168    * `descriptor_index` - Entity descriptor index
169
170    # Panics
171    Panics if `min_ruin_count` is 0 or `max_ruin_count < min_ruin_count`.
172    */
173    #[allow(clippy::too_many_arguments)]
174    pub fn new(
175        min_ruin_count: usize,
176        max_ruin_count: usize,
177        entity_count: fn(&S) -> usize,
178        list_len: fn(&S, usize) -> usize,
179        list_get: fn(&S, usize, usize) -> Option<V>,
180        list_remove: fn(&mut S, usize, usize) -> V,
181        list_insert: fn(&mut S, usize, usize, V),
182        variable_name: &'static str,
183        descriptor_index: usize,
184    ) -> Self {
185        assert!(min_ruin_count >= 1, "min_ruin_count must be at least 1");
186        assert!(
187            max_ruin_count >= min_ruin_count,
188            "max_ruin_count must be >= min_ruin_count"
189        );
190
191        Self {
192            min_ruin_count,
193            max_ruin_count,
194            rng: RefCell::new(SmallRng::from_rng(&mut rand::rng())),
195            entity_count,
196            list_len,
197            list_get,
198            list_remove,
199            list_insert,
200            element_owner_fn: None,
201            precedence_element_count: None,
202            precedence_index_to_element: None,
203            precedence_successors_fn: None,
204            variable_name,
205            descriptor_index,
206            moves_per_step: 10,
207            max_source_list_len: None,
208            skip_empty_destinations: false,
209            _phantom: PhantomData,
210        }
211    }
212
213    /// Sets the number of ruin moves to generate per iteration.
214    ///
215    /// Default is 10.
216    pub fn with_moves_per_step(mut self, count: usize) -> Self {
217        self.moves_per_step = count;
218        self
219    }
220
221    pub fn with_max_source_list_len(mut self, max_source_list_len: Option<usize>) -> Self {
222        self.max_source_list_len = max_source_list_len;
223        self
224    }
225
226    pub fn with_skip_empty_destinations(mut self, skip_empty_destinations: bool) -> Self {
227        self.skip_empty_destinations = skip_empty_destinations;
228        self
229    }
230
231    pub fn with_seed(mut self, seed: u64) -> Self {
232        self.rng = RefCell::new(SmallRng::seed_from_u64(seed));
233        self
234    }
235
236    pub fn with_element_owner_fn(
237        mut self,
238        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
239    ) -> Self {
240        self.element_owner_fn = element_owner_fn;
241        self
242    }
243
244    pub(crate) fn with_precedence_hooks(
245        mut self,
246        element_count: Option<fn(&S) -> usize>,
247        index_to_element: Option<fn(&S, usize) -> V>,
248        successors_fn: Option<fn(&S, V, &mut Vec<V>)>,
249    ) -> Self {
250        self.precedence_element_count = element_count;
251        self.precedence_index_to_element = index_to_element;
252        self.precedence_successors_fn = successors_fn;
253        self
254    }
255}
256
257enum ListRuinSourcePool {
258    Unrestricted(Vec<(usize, usize)>),
259    OwnerRestricted(Vec<(usize, SmallVec<[usize; 8]>)>),
260}
261
262impl ListRuinSourcePool {
263    fn is_empty(&self) -> bool {
264        match self {
265            Self::Unrestricted(entities) => entities.is_empty(),
266            Self::OwnerRestricted(entities) => entities.is_empty(),
267        }
268    }
269}
270
271pub struct ListRuinMoveCursor<S, V>
272where
273    S: PlanningSolution,
274    V: Clone + PartialEq + Send + Sync + Debug + 'static,
275{
276    store: CandidateStore<S, ListRuinMove<S, V>>,
277    rng: SmallRng,
278    source_pool: ListRuinSourcePool,
279    remaining_moves: usize,
280    min_ruin_count: usize,
281    max_ruin_count: usize,
282    entity_count: fn(&S) -> usize,
283    list_len: fn(&S, usize) -> usize,
284    list_get: fn(&S, usize, usize) -> Option<V>,
285    list_remove: fn(&mut S, usize, usize) -> V,
286    list_insert: fn(&mut S, usize, usize, V),
287    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
288    precedence_element_count: Option<fn(&S) -> usize>,
289    precedence_index_to_element: Option<fn(&S, usize) -> V>,
290    precedence_successors_fn: Option<fn(&S, V, &mut Vec<V>)>,
291    skip_empty_destinations: bool,
292    variable_name: &'static str,
293    descriptor_index: usize,
294}
295
296impl<S, V> ListRuinMoveCursor<S, V>
297where
298    S: PlanningSolution,
299    V: Clone + PartialEq + Send + Sync + Debug + 'static,
300{
301    #[allow(clippy::too_many_arguments)]
302    fn new(
303        rng: SmallRng,
304        source_pool: ListRuinSourcePool,
305        remaining_moves: usize,
306        min_ruin_count: usize,
307        max_ruin_count: usize,
308        entity_count: fn(&S) -> usize,
309        list_len: fn(&S, usize) -> usize,
310        list_get: fn(&S, usize, usize) -> Option<V>,
311        list_remove: fn(&mut S, usize, usize) -> V,
312        list_insert: fn(&mut S, usize, usize, V),
313        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
314        precedence_element_count: Option<fn(&S) -> usize>,
315        precedence_index_to_element: Option<fn(&S, usize) -> V>,
316        precedence_successors_fn: Option<fn(&S, V, &mut Vec<V>)>,
317        skip_empty_destinations: bool,
318        variable_name: &'static str,
319        descriptor_index: usize,
320    ) -> Self {
321        Self {
322            store: CandidateStore::new(),
323            rng,
324            source_pool,
325            remaining_moves,
326            min_ruin_count,
327            max_ruin_count,
328            entity_count,
329            list_len,
330            list_get,
331            list_remove,
332            list_insert,
333            element_owner_fn,
334            precedence_element_count,
335            precedence_index_to_element,
336            precedence_successors_fn,
337            skip_empty_destinations,
338            variable_name,
339            descriptor_index,
340        }
341    }
342
343    fn choose_ruin_count(&mut self, eligible_len: usize) -> usize {
344        let min = self.min_ruin_count.min(eligible_len);
345        let max = self.max_ruin_count.min(eligible_len);
346        if min == max {
347            min
348        } else {
349            self.rng.random_range(min..=max)
350        }
351    }
352
353    fn next_unrestricted_move(&mut self) -> Option<ListRuinMove<S, V>> {
354        let ListRuinSourcePool::Unrestricted(entities) = &self.source_pool else {
355            return None;
356        };
357        let &(entity_idx, list_length) = entities.get(self.rng.random_range(0..entities.len()))?;
358        let ruin_count = self.choose_ruin_count(list_length);
359        let mut indices: SmallVec<[usize; 8]> = (0..list_length).collect();
360        for i in 0..ruin_count {
361            let j = self.rng.random_range(i..list_length);
362            indices.swap(i, j);
363        }
364        indices.truncate(ruin_count);
365        Some(self.build_move(entity_idx, &indices))
366    }
367
368    fn next_owner_restricted_move(&mut self) -> Option<ListRuinMove<S, V>> {
369        let (entity_idx, mut indices) = {
370            let ListRuinSourcePool::OwnerRestricted(entities) = &self.source_pool else {
371                return None;
372            };
373            let (entity_idx, eligible_indices) =
374                entities.get(self.rng.random_range(0..entities.len()))?;
375            (*entity_idx, eligible_indices.clone())
376        };
377        let eligible_len = indices.len();
378        let ruin_count = self.choose_ruin_count(eligible_len);
379        for i in 0..ruin_count {
380            let j = self.rng.random_range(i..eligible_len);
381            indices.swap(i, j);
382        }
383        indices.truncate(ruin_count);
384        Some(self.build_move(entity_idx, &indices))
385    }
386
387    fn build_move(&self, entity_idx: usize, indices: &[usize]) -> ListRuinMove<S, V> {
388        ListRuinMove::new(
389            entity_idx,
390            indices,
391            self.entity_count,
392            self.list_len,
393            self.list_get,
394            self.list_remove,
395            self.list_insert,
396            self.variable_name,
397            self.descriptor_index,
398        )
399        .with_element_owner_fn(self.element_owner_fn)
400        .with_precedence_hooks(
401            self.precedence_element_count,
402            self.precedence_index_to_element,
403            self.precedence_successors_fn,
404        )
405        .with_skip_empty_destinations(self.skip_empty_destinations)
406    }
407}
408
409impl<S, V> MoveCursor<S, ListRuinMove<S, V>> for ListRuinMoveCursor<S, V>
410where
411    S: PlanningSolution,
412    V: Clone + PartialEq + Send + Sync + Debug + 'static,
413{
414    fn next_candidate(&mut self) -> Option<CandidateId> {
415        if self.remaining_moves == 0 || self.source_pool.is_empty() {
416            return None;
417        }
418        self.remaining_moves -= 1;
419
420        let next_move = match self.source_pool {
421            ListRuinSourcePool::Unrestricted(_) => self.next_unrestricted_move(),
422            ListRuinSourcePool::OwnerRestricted(_) => self.next_owner_restricted_move(),
423        }?;
424        Some(self.store.push(next_move))
425    }
426
427    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListRuinMove<S, V>>> {
428        self.store.candidate(id)
429    }
430
431    fn take_candidate(&mut self, id: CandidateId) -> ListRuinMove<S, V> {
432        self.store.take_candidate(id)
433    }
434}
435
436impl<S, V> MoveSelector<S, ListRuinMove<S, V>> for ListRuinMoveSelector<S, V>
437where
438    S: PlanningSolution,
439    V: Clone + PartialEq + Send + Sync + Debug + 'static,
440{
441    type Cursor<'a>
442        = ListRuinMoveCursor<S, V>
443    where
444        Self: 'a;
445
446    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
447        self.open_cursor_with_context(score_director, MoveStreamContext::default())
448    }
449
450    fn open_cursor_with_context<'a, D: Director<S>>(
451        &'a self,
452        score_director: &D,
453        context: MoveStreamContext,
454    ) -> Self::Cursor<'a> {
455        let solution = score_director.working_solution();
456        let total_entities = (self.entity_count)(solution);
457        let non_empty_entities: Vec<(usize, usize)> = (0..total_entities)
458            .filter_map(|entity_idx| {
459                let len = (self.list_len)(solution, entity_idx);
460                (len > 0
461                    && self
462                        .max_source_list_len
463                        .is_none_or(|max_len| len <= max_len))
464                .then_some((entity_idx, len))
465            })
466            .collect();
467
468        let source_pool = if let Some(owner_fn) = self.element_owner_fn {
469            let owner_eligible_entities = non_empty_entities
470                .iter()
471                .filter_map(|&(entity_idx, list_length)| {
472                    let mut eligible_indices = SmallVec::new();
473                    for pos in 0..list_length {
474                        let Some(element) = (self.list_get)(solution, entity_idx, pos) else {
475                            continue;
476                        };
477                        if crate::list_placement::candidate_entity_indices(
478                            Some(owner_fn),
479                            solution,
480                            total_entities,
481                            &element,
482                        )
483                        .next()
484                        .is_some()
485                        {
486                            eligible_indices.push(pos);
487                        }
488                    }
489                    (!eligible_indices.is_empty()).then_some((entity_idx, eligible_indices))
490                })
491                .collect();
492            ListRuinSourcePool::OwnerRestricted(owner_eligible_entities)
493        } else {
494            ListRuinSourcePool::Unrestricted(non_empty_entities)
495        };
496
497        let seed = self.rng.borrow_mut().random::<u64>()
498            ^ context.offset_seed(0x7157_8011_C0DE_0001) as u64;
499        ListRuinMoveCursor::new(
500            SmallRng::seed_from_u64(seed),
501            source_pool,
502            self.moves_per_step,
503            self.min_ruin_count,
504            self.max_ruin_count,
505            self.entity_count,
506            self.list_len,
507            self.list_get,
508            self.list_remove,
509            self.list_insert,
510            self.element_owner_fn,
511            self.precedence_element_count,
512            self.precedence_index_to_element,
513            self.precedence_successors_fn,
514            self.skip_empty_destinations,
515            self.variable_name,
516            self.descriptor_index,
517        )
518    }
519
520    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
521        let total = (self.entity_count)(score_director.working_solution());
522        if total == 0 {
523            return 0;
524        }
525        self.moves_per_step
526    }
527
528    fn is_never_ending(&self) -> bool {
529        false
530    }
531}
solverforge_solver/heuristic/selector/list_ruin.rs

solverforge_solver/heuristic/selector/
list_ruin.rs
