solverforge_solver/builder/
list_selector.rs

1// List variable move selector enum and builder.
2
3use std::fmt::Debug;
4
5use solverforge_config::MoveSelectorConfig;
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::{ListMoveImpl, MoveArena};
10use crate::heuristic::selector::decorator::VecUnionSelector;
11use crate::heuristic::selector::k_opt::KOptConfig;
12use crate::heuristic::selector::move_selector::{
13    ListMoveKOptSelector, ListMoveListChangeSelector, ListMoveListRuinSelector,
14    ListMoveNearbyKOptSelector, MoveSelector,
15};
16use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
17
18use super::context::IntraDistanceAdapter;
19use crate::heuristic::selector::{
20    FromSolutionEntitySelector, ListMoveListReverseSelector, ListMoveListSwapSelector,
21    ListMoveNearbyListChangeSelector, ListMoveNearbyListSwapSelector,
22    ListMoveSubListChangeSelector, ListMoveSubListSwapSelector,
23};
24
25use super::context::ListContext;
26
27/// A monomorphized leaf selector for list planning variables.
28///
29/// Each variant wraps one of the available list move selector wrapper types.
30/// Allows `VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>` to have
31/// a single concrete type regardless of configuration.
32pub enum ListLeafSelector<S, V, DM, IDM>
33where
34    S: PlanningSolution,
35    V: Clone + PartialEq + Send + Sync + Debug + 'static,
36    DM: CrossEntityDistanceMeter<S>,
37    IDM: CrossEntityDistanceMeter<S>,
38{
39    // Nearby list change (distance-pruned relocation).
40    NearbyListChange(ListMoveNearbyListChangeSelector<S, V, DM, FromSolutionEntitySelector>),
41    // Nearby list swap (distance-pruned swap).
42    NearbyListSwap(ListMoveNearbyListSwapSelector<S, V, IDM, FromSolutionEntitySelector>),
43    // List reverse (2-opt).
44    ListReverse(ListMoveListReverseSelector<S, V, FromSolutionEntitySelector>),
45    // Sublist change (Or-opt).
46    SubListChange(ListMoveSubListChangeSelector<S, V, FromSolutionEntitySelector>),
47    // K-opt.
48    KOpt(ListMoveKOptSelector<S, V, FromSolutionEntitySelector>),
49    // Nearby k-opt (distance-pruned).
50    NearbyKOpt(
51        ListMoveNearbyKOptSelector<S, V, IntraDistanceAdapter<IDM>, FromSolutionEntitySelector>,
52    ),
53    // List ruin (LNS).
54    ListRuin(ListMoveListRuinSelector<S, V>),
55    // Full list change (unrestricted relocation).
56    ListChange(ListMoveListChangeSelector<S, V, FromSolutionEntitySelector>),
57    // Full list swap (unrestricted swap).
58    ListSwap(ListMoveListSwapSelector<S, V, FromSolutionEntitySelector>),
59    // Sublist swap.
60    SubListSwap(ListMoveSubListSwapSelector<S, V, FromSolutionEntitySelector>),
61}
62
63impl<S, V, DM, IDM> Debug for ListLeafSelector<S, V, DM, IDM>
64where
65    S: PlanningSolution,
66    V: Clone + PartialEq + Send + Sync + Debug + 'static,
67    DM: CrossEntityDistanceMeter<S>,
68    IDM: CrossEntityDistanceMeter<S>,
69{
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        match self {
72            Self::NearbyListChange(s) => write!(f, "ListLeafSelector::NearbyListChange({s:?})"),
73            Self::NearbyListSwap(s) => write!(f, "ListLeafSelector::NearbyListSwap({s:?})"),
74            Self::ListReverse(s) => write!(f, "ListLeafSelector::ListReverse({s:?})"),
75            Self::SubListChange(s) => write!(f, "ListLeafSelector::SubListChange({s:?})"),
76            Self::KOpt(s) => write!(f, "ListLeafSelector::KOpt({s:?})"),
77            Self::NearbyKOpt(s) => write!(f, "ListLeafSelector::NearbyKOpt({s:?})"),
78            Self::ListRuin(s) => write!(f, "ListLeafSelector::ListRuin({s:?})"),
79            Self::ListChange(s) => write!(f, "ListLeafSelector::ListChange({s:?})"),
80            Self::ListSwap(s) => write!(f, "ListLeafSelector::ListSwap({s:?})"),
81            Self::SubListSwap(s) => write!(f, "ListLeafSelector::SubListSwap({s:?})"),
82        }
83    }
84}
85
86impl<S, V, DM, IDM> MoveSelector<S, ListMoveImpl<S, V>> for ListLeafSelector<S, V, DM, IDM>
87where
88    S: PlanningSolution,
89    V: Clone + PartialEq + Send + Sync + Debug + 'static,
90    DM: CrossEntityDistanceMeter<S>,
91    IDM: CrossEntityDistanceMeter<S> + 'static,
92{
93    fn iter_moves<'a, D: Director<S>>(
94        &'a self,
95        score_director: &'a D,
96    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
97        enum ListLeafIter<A, B, C, DIter, E, F, G, H, I, J> {
98            NearbyListChange(A),
99            NearbyListSwap(B),
100            ListReverse(C),
101            SubListChange(DIter),
102            KOpt(E),
103            NearbyKOpt(F),
104            ListRuin(G),
105            ListChange(H),
106            ListSwap(I),
107            SubListSwap(J),
108        }
109
110        impl<T, A, B, C, DIter, E, F, G, H, I, J> Iterator
111            for ListLeafIter<A, B, C, DIter, E, F, G, H, I, J>
112        where
113            A: Iterator<Item = T>,
114            B: Iterator<Item = T>,
115            C: Iterator<Item = T>,
116            DIter: Iterator<Item = T>,
117            E: Iterator<Item = T>,
118            F: Iterator<Item = T>,
119            G: Iterator<Item = T>,
120            H: Iterator<Item = T>,
121            I: Iterator<Item = T>,
122            J: Iterator<Item = T>,
123        {
124            type Item = T;
125
126            fn next(&mut self) -> Option<Self::Item> {
127                match self {
128                    Self::NearbyListChange(iter) => iter.next(),
129                    Self::NearbyListSwap(iter) => iter.next(),
130                    Self::ListReverse(iter) => iter.next(),
131                    Self::SubListChange(iter) => iter.next(),
132                    Self::KOpt(iter) => iter.next(),
133                    Self::NearbyKOpt(iter) => iter.next(),
134                    Self::ListRuin(iter) => iter.next(),
135                    Self::ListChange(iter) => iter.next(),
136                    Self::ListSwap(iter) => iter.next(),
137                    Self::SubListSwap(iter) => iter.next(),
138                }
139            }
140        }
141
142        match self {
143            Self::NearbyListChange(s) => {
144                ListLeafIter::NearbyListChange(s.iter_moves(score_director))
145            }
146            Self::NearbyListSwap(s) => ListLeafIter::NearbyListSwap(s.iter_moves(score_director)),
147            Self::ListReverse(s) => ListLeafIter::ListReverse(s.iter_moves(score_director)),
148            Self::SubListChange(s) => ListLeafIter::SubListChange(s.iter_moves(score_director)),
149            Self::KOpt(s) => ListLeafIter::KOpt(s.iter_moves(score_director)),
150            Self::NearbyKOpt(s) => ListLeafIter::NearbyKOpt(s.iter_moves(score_director)),
151            Self::ListRuin(s) => ListLeafIter::ListRuin(s.iter_moves(score_director)),
152            Self::ListChange(s) => ListLeafIter::ListChange(s.iter_moves(score_director)),
153            Self::ListSwap(s) => ListLeafIter::ListSwap(s.iter_moves(score_director)),
154            Self::SubListSwap(s) => ListLeafIter::SubListSwap(s.iter_moves(score_director)),
155        }
156    }
157
158    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
159        match self {
160            Self::NearbyListChange(s) => s.size(score_director),
161            Self::NearbyListSwap(s) => s.size(score_director),
162            Self::ListReverse(s) => s.size(score_director),
163            Self::SubListChange(s) => s.size(score_director),
164            Self::KOpt(s) => s.size(score_director),
165            Self::NearbyKOpt(s) => s.size(score_director),
166            Self::ListRuin(s) => s.size(score_director),
167            Self::ListChange(s) => s.size(score_director),
168            Self::ListSwap(s) => s.size(score_director),
169            Self::SubListSwap(s) => s.size(score_director),
170        }
171    }
172
173    fn append_moves<D: Director<S>>(
174        &self,
175        score_director: &D,
176        arena: &mut MoveArena<ListMoveImpl<S, V>>,
177    ) {
178        match self {
179            Self::NearbyListChange(s) => arena.extend(s.iter_moves(score_director)),
180            Self::NearbyListSwap(s) => arena.extend(s.iter_moves(score_director)),
181            Self::ListReverse(s) => arena.extend(s.iter_moves(score_director)),
182            Self::SubListChange(s) => arena.extend(s.iter_moves(score_director)),
183            Self::KOpt(s) => arena.extend(s.iter_moves(score_director)),
184            Self::NearbyKOpt(s) => arena.extend(s.iter_moves(score_director)),
185            Self::ListRuin(s) => arena.extend(s.iter_moves(score_director)),
186            Self::ListChange(s) => arena.extend(s.iter_moves(score_director)),
187            Self::ListSwap(s) => arena.extend(s.iter_moves(score_director)),
188            Self::SubListSwap(s) => arena.extend(s.iter_moves(score_director)),
189        }
190    }
191}
192
193/// Builder that constructs a `VecUnionSelector` of `ListLeafSelector` from config.
194pub struct ListMoveSelectorBuilder;
195
196impl ListMoveSelectorBuilder {
197    /// Builds a `VecUnionSelector` from move selector config and domain context.
198    ///
199    /// Default (no config): `Union(NearbyListChange(20), NearbyListSwap(20), ListReverse)`
200    pub fn build<S, V, DM, IDM>(
201        config: Option<&MoveSelectorConfig>,
202        ctx: &ListContext<S, V, DM, IDM>,
203    ) -> VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>
204    where
205        S: PlanningSolution,
206        V: Clone + PartialEq + Send + Sync + Debug + 'static,
207        DM: CrossEntityDistanceMeter<S> + Clone,
208        IDM: CrossEntityDistanceMeter<S> + Clone,
209    {
210        let mut leaves: Vec<ListLeafSelector<S, V, DM, IDM>> = Vec::new();
211        match config {
212            None => {
213                Self::push_nearby_change(&mut leaves, ctx, 20);
214                Self::push_nearby_swap(&mut leaves, ctx, 20);
215                Self::push_list_reverse(&mut leaves, ctx);
216            }
217            Some(cfg) => Self::collect_leaves(cfg, ctx, &mut leaves),
218        }
219        assert!(
220            !leaves.is_empty(),
221            "stock move selector configuration produced no list neighborhoods"
222        );
223        VecUnionSelector::new(leaves)
224    }
225
226    fn collect_leaves<S, V, DM, IDM>(
227        config: &MoveSelectorConfig,
228        ctx: &ListContext<S, V, DM, IDM>,
229        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
230    ) where
231        S: PlanningSolution,
232        V: Clone + PartialEq + Send + Sync + Debug + 'static,
233        DM: CrossEntityDistanceMeter<S> + Clone,
234        IDM: CrossEntityDistanceMeter<S> + Clone,
235    {
236        match config {
237            MoveSelectorConfig::NearbyListChangeMoveSelector(c) => {
238                Self::push_nearby_change(out, ctx, c.max_nearby);
239            }
240            MoveSelectorConfig::NearbyListSwapMoveSelector(c) => {
241                Self::push_nearby_swap(out, ctx, c.max_nearby);
242            }
243            MoveSelectorConfig::ListReverseMoveSelector(_) => {
244                Self::push_list_reverse(out, ctx);
245            }
246            MoveSelectorConfig::SubListChangeMoveSelector(c) => {
247                Self::push_sublist_change(out, ctx, c.min_sublist_size, c.max_sublist_size);
248            }
249            MoveSelectorConfig::SubListSwapMoveSelector(c) => {
250                Self::push_sublist_swap(out, ctx, c.min_sublist_size, c.max_sublist_size);
251            }
252            MoveSelectorConfig::KOptMoveSelector(c) => {
253                Self::push_kopt(out, ctx, c.k, c.min_segment_len, c.max_nearby);
254            }
255            MoveSelectorConfig::ListRuinMoveSelector(c) => {
256                Self::push_list_ruin(out, ctx, c.min_ruin_count, c.max_ruin_count);
257            }
258            MoveSelectorConfig::ListChangeMoveSelector(_) => {
259                Self::push_list_change(out, ctx);
260            }
261            MoveSelectorConfig::ListSwapMoveSelector(_) => {
262                Self::push_list_swap(out, ctx);
263            }
264            MoveSelectorConfig::UnionMoveSelector(u) => {
265                for child in &u.selectors {
266                    Self::collect_leaves(child, ctx, out);
267                }
268            }
269            MoveSelectorConfig::ChangeMoveSelector(_) | MoveSelectorConfig::SwapMoveSelector(_) => {
270                panic!("standard move selector configured against a list-variable stock context");
271            }
272            MoveSelectorConfig::CartesianProductMoveSelector(_) => {
273                panic!("cartesian_product move selectors are not supported in stock solving");
274            }
275        }
276    }
277
278    fn push_nearby_change<S, V, DM, IDM>(
279        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
280        ctx: &ListContext<S, V, DM, IDM>,
281        max_nearby: usize,
282    ) where
283        S: PlanningSolution,
284        V: Clone + PartialEq + Send + Sync + Debug + 'static,
285        DM: CrossEntityDistanceMeter<S> + Clone,
286        IDM: CrossEntityDistanceMeter<S> + Clone,
287    {
288        use crate::heuristic::selector::nearby_list_change::NearbyListChangeMoveSelector;
289
290        let inner = NearbyListChangeMoveSelector::new(
291            FromSolutionEntitySelector::new(ctx.descriptor_index),
292            ctx.cross_distance_meter.clone(),
293            max_nearby,
294            ctx.list_len,
295            ctx.list_remove,
296            ctx.list_insert,
297            ctx.variable_name,
298            ctx.descriptor_index,
299        );
300        out.push(ListLeafSelector::NearbyListChange(
301            ListMoveNearbyListChangeSelector::new(inner),
302        ));
303    }
304
305    fn push_nearby_swap<S, V, DM, IDM>(
306        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
307        ctx: &ListContext<S, V, DM, IDM>,
308        max_nearby: usize,
309    ) where
310        S: PlanningSolution,
311        V: Clone + PartialEq + Send + Sync + Debug + 'static,
312        DM: CrossEntityDistanceMeter<S> + Clone,
313        IDM: CrossEntityDistanceMeter<S> + Clone,
314    {
315        use crate::heuristic::selector::nearby_list_swap::NearbyListSwapMoveSelector;
316
317        let inner = NearbyListSwapMoveSelector::new(
318            FromSolutionEntitySelector::new(ctx.descriptor_index),
319            ctx.intra_distance_meter.clone(),
320            max_nearby,
321            ctx.list_len,
322            ctx.list_get,
323            ctx.list_set,
324            ctx.variable_name,
325            ctx.descriptor_index,
326        );
327        out.push(ListLeafSelector::NearbyListSwap(
328            ListMoveNearbyListSwapSelector::new(inner),
329        ));
330    }
331
332    fn push_list_reverse<S, V, DM, IDM>(
333        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
334        ctx: &ListContext<S, V, DM, IDM>,
335    ) where
336        S: PlanningSolution,
337        V: Clone + PartialEq + Send + Sync + Debug + 'static,
338        DM: CrossEntityDistanceMeter<S> + Clone,
339        IDM: CrossEntityDistanceMeter<S> + Clone,
340    {
341        use crate::heuristic::selector::list_reverse::ListReverseMoveSelector;
342
343        let inner = ListReverseMoveSelector::new(
344            FromSolutionEntitySelector::new(ctx.descriptor_index),
345            ctx.list_len,
346            ctx.list_reverse,
347            ctx.variable_name,
348            ctx.descriptor_index,
349        );
350        out.push(ListLeafSelector::ListReverse(
351            ListMoveListReverseSelector::new(inner),
352        ));
353    }
354
355    fn push_sublist_change<S, V, DM, IDM>(
356        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
357        ctx: &ListContext<S, V, DM, IDM>,
358        min_sublist_size: usize,
359        max_sublist_size: usize,
360    ) where
361        S: PlanningSolution,
362        V: Clone + PartialEq + Send + Sync + Debug + 'static,
363        DM: CrossEntityDistanceMeter<S> + Clone,
364        IDM: CrossEntityDistanceMeter<S> + Clone,
365    {
366        use crate::heuristic::selector::sublist_change::SubListChangeMoveSelector;
367
368        let inner = SubListChangeMoveSelector::new(
369            FromSolutionEntitySelector::new(ctx.descriptor_index),
370            min_sublist_size,
371            max_sublist_size,
372            ctx.list_len,
373            ctx.sublist_remove,
374            ctx.sublist_insert,
375            ctx.variable_name,
376            ctx.descriptor_index,
377        );
378        out.push(ListLeafSelector::SubListChange(
379            ListMoveSubListChangeSelector::new(inner),
380        ));
381    }
382
383    fn push_sublist_swap<S, V, DM, IDM>(
384        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
385        ctx: &ListContext<S, V, DM, IDM>,
386        min_sublist_size: usize,
387        max_sublist_size: usize,
388    ) where
389        S: PlanningSolution,
390        V: Clone + PartialEq + Send + Sync + Debug + 'static,
391        DM: CrossEntityDistanceMeter<S> + Clone,
392        IDM: CrossEntityDistanceMeter<S> + Clone,
393    {
394        use crate::heuristic::selector::sublist_swap::SubListSwapMoveSelector;
395
396        let inner = SubListSwapMoveSelector::new(
397            FromSolutionEntitySelector::new(ctx.descriptor_index),
398            min_sublist_size,
399            max_sublist_size,
400            ctx.list_len,
401            ctx.sublist_remove,
402            ctx.sublist_insert,
403            ctx.variable_name,
404            ctx.descriptor_index,
405        );
406        out.push(ListLeafSelector::SubListSwap(
407            ListMoveSubListSwapSelector::new(inner),
408        ));
409    }
410
411    fn push_kopt<S, V, DM, IDM>(
412        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
413        ctx: &ListContext<S, V, DM, IDM>,
414        k: usize,
415        min_segment_len: usize,
416        max_nearby: usize,
417    ) where
418        S: PlanningSolution,
419        V: Clone + PartialEq + Send + Sync + Debug + 'static,
420        DM: CrossEntityDistanceMeter<S> + Clone,
421        IDM: CrossEntityDistanceMeter<S> + Clone,
422    {
423        use crate::heuristic::selector::k_opt::{KOptMoveSelector, NearbyKOptMoveSelector};
424
425        let config = KOptConfig::new(k.clamp(2, 5)).with_min_segment_len(min_segment_len);
426        if max_nearby > 0 {
427            let adapter = IntraDistanceAdapter(ctx.intra_distance_meter.clone());
428            let inner = NearbyKOptMoveSelector::new(
429                FromSolutionEntitySelector::new(ctx.descriptor_index),
430                adapter,
431                max_nearby,
432                config,
433                ctx.list_len,
434                ctx.sublist_remove,
435                ctx.sublist_insert,
436                ctx.variable_name,
437                ctx.descriptor_index,
438            );
439            out.push(ListLeafSelector::NearbyKOpt(
440                ListMoveNearbyKOptSelector::new(inner),
441            ));
442        } else {
443            let inner = KOptMoveSelector::new(
444                FromSolutionEntitySelector::new(ctx.descriptor_index),
445                config,
446                ctx.list_len,
447                ctx.sublist_remove,
448                ctx.sublist_insert,
449                ctx.variable_name,
450                ctx.descriptor_index,
451            );
452            out.push(ListLeafSelector::KOpt(ListMoveKOptSelector::new(inner)));
453        }
454    }
455
456    fn push_list_ruin<S, V, DM, IDM>(
457        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
458        ctx: &ListContext<S, V, DM, IDM>,
459        min_ruin_count: usize,
460        max_ruin_count: usize,
461    ) where
462        S: PlanningSolution,
463        V: Clone + PartialEq + Send + Sync + Debug + 'static,
464        DM: CrossEntityDistanceMeter<S> + Clone,
465        IDM: CrossEntityDistanceMeter<S> + Clone,
466    {
467        use crate::heuristic::selector::list_ruin::ListRuinMoveSelector;
468
469        let inner = ListRuinMoveSelector::new(
470            min_ruin_count.max(1),
471            max_ruin_count.max(1),
472            ctx.entity_count,
473            ctx.list_len,
474            ctx.ruin_remove,
475            ctx.ruin_insert,
476            ctx.variable_name,
477            ctx.descriptor_index,
478        );
479        out.push(ListLeafSelector::ListRuin(ListMoveListRuinSelector::new(
480            inner,
481        )));
482    }
483
484    fn push_list_change<S, V, DM, IDM>(
485        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
486        ctx: &ListContext<S, V, DM, IDM>,
487    ) where
488        S: PlanningSolution,
489        V: Clone + PartialEq + Send + Sync + Debug + 'static,
490        DM: CrossEntityDistanceMeter<S> + Clone,
491        IDM: CrossEntityDistanceMeter<S> + Clone,
492    {
493        use crate::heuristic::selector::list_change::ListChangeMoveSelector;
494
495        let inner = ListChangeMoveSelector::new(
496            FromSolutionEntitySelector::new(ctx.descriptor_index),
497            ctx.list_len,
498            ctx.list_remove,
499            ctx.list_insert,
500            ctx.variable_name,
501            ctx.descriptor_index,
502        );
503        out.push(ListLeafSelector::ListChange(
504            ListMoveListChangeSelector::new(inner),
505        ));
506    }
507
508    fn push_list_swap<S, V, DM, IDM>(
509        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
510        ctx: &ListContext<S, V, DM, IDM>,
511    ) where
512        S: PlanningSolution,
513        V: Clone + PartialEq + Send + Sync + Debug + 'static,
514        DM: CrossEntityDistanceMeter<S> + Clone,
515        IDM: CrossEntityDistanceMeter<S> + Clone,
516    {
517        use crate::heuristic::selector::list_swap::ListSwapMoveSelector;
518
519        let inner = ListSwapMoveSelector::new(
520            FromSolutionEntitySelector::new(ctx.descriptor_index),
521            ctx.list_len,
522            ctx.list_get,
523            ctx.list_set,
524            ctx.variable_name,
525            ctx.descriptor_index,
526        );
527        out.push(ListLeafSelector::ListSwap(ListMoveListSwapSelector::new(
528            inner,
529        )));
530    }
531}
solverforge_solver/builder/list_selector.rs

solverforge_solver/builder/
list_selector.rs
