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        let moves: Vec<ListMoveImpl<S, V>> = match self {
98            Self::NearbyListChange(s) => s.iter_moves(score_director).collect(),
99            Self::NearbyListSwap(s) => s.iter_moves(score_director).collect(),
100            Self::ListReverse(s) => s.iter_moves(score_director).collect(),
101            Self::SubListChange(s) => s.iter_moves(score_director).collect(),
102            Self::KOpt(s) => s.iter_moves(score_director).collect(),
103            Self::NearbyKOpt(s) => s.iter_moves(score_director).collect(),
104            Self::ListRuin(s) => s.iter_moves(score_director).collect(),
105            Self::ListChange(s) => s.iter_moves(score_director).collect(),
106            Self::ListSwap(s) => s.iter_moves(score_director).collect(),
107            Self::SubListSwap(s) => s.iter_moves(score_director).collect(),
108        };
109        moves.into_iter()
110    }
111
112    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
113        match self {
114            Self::NearbyListChange(s) => s.size(score_director),
115            Self::NearbyListSwap(s) => s.size(score_director),
116            Self::ListReverse(s) => s.size(score_director),
117            Self::SubListChange(s) => s.size(score_director),
118            Self::KOpt(s) => s.size(score_director),
119            Self::NearbyKOpt(s) => s.size(score_director),
120            Self::ListRuin(s) => s.size(score_director),
121            Self::ListChange(s) => s.size(score_director),
122            Self::ListSwap(s) => s.size(score_director),
123            Self::SubListSwap(s) => s.size(score_director),
124        }
125    }
126
127    fn append_moves<D: Director<S>>(
128        &self,
129        score_director: &D,
130        arena: &mut MoveArena<ListMoveImpl<S, V>>,
131    ) {
132        match self {
133            Self::NearbyListChange(s) => arena.extend(s.iter_moves(score_director)),
134            Self::NearbyListSwap(s) => arena.extend(s.iter_moves(score_director)),
135            Self::ListReverse(s) => arena.extend(s.iter_moves(score_director)),
136            Self::SubListChange(s) => arena.extend(s.iter_moves(score_director)),
137            Self::KOpt(s) => arena.extend(s.iter_moves(score_director)),
138            Self::NearbyKOpt(s) => arena.extend(s.iter_moves(score_director)),
139            Self::ListRuin(s) => arena.extend(s.iter_moves(score_director)),
140            Self::ListChange(s) => arena.extend(s.iter_moves(score_director)),
141            Self::ListSwap(s) => arena.extend(s.iter_moves(score_director)),
142            Self::SubListSwap(s) => arena.extend(s.iter_moves(score_director)),
143        }
144    }
145}
146
147/// Builder that constructs a `VecUnionSelector` of `ListLeafSelector` from config.
148pub struct ListMoveSelectorBuilder;
149
150impl ListMoveSelectorBuilder {
151    /// Builds a `VecUnionSelector` from move selector config and domain context.
152    ///
153    /// Default (no config): `Union(NearbyListChange(20), NearbyListSwap(20), ListReverse)`
154    pub fn build<S, V, DM, IDM>(
155        config: Option<&MoveSelectorConfig>,
156        ctx: &ListContext<S, V, DM, IDM>,
157    ) -> VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>
158    where
159        S: PlanningSolution,
160        V: Clone + PartialEq + Send + Sync + Debug + 'static,
161        DM: CrossEntityDistanceMeter<S> + Clone,
162        IDM: CrossEntityDistanceMeter<S> + Clone,
163    {
164        let mut leaves: Vec<ListLeafSelector<S, V, DM, IDM>> = Vec::new();
165        match config {
166            None => {
167                Self::push_nearby_change(&mut leaves, ctx, 20);
168                Self::push_nearby_swap(&mut leaves, ctx, 20);
169                Self::push_list_reverse(&mut leaves, ctx);
170            }
171            Some(cfg) => Self::collect_leaves(cfg, ctx, &mut leaves),
172        }
173        assert!(
174            !leaves.is_empty(),
175            "stock move selector configuration produced no list neighborhoods"
176        );
177        VecUnionSelector::new(leaves)
178    }
179
180    fn collect_leaves<S, V, DM, IDM>(
181        config: &MoveSelectorConfig,
182        ctx: &ListContext<S, V, DM, IDM>,
183        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
184    ) where
185        S: PlanningSolution,
186        V: Clone + PartialEq + Send + Sync + Debug + 'static,
187        DM: CrossEntityDistanceMeter<S> + Clone,
188        IDM: CrossEntityDistanceMeter<S> + Clone,
189    {
190        match config {
191            MoveSelectorConfig::NearbyListChangeMoveSelector(c) => {
192                Self::push_nearby_change(out, ctx, c.max_nearby);
193            }
194            MoveSelectorConfig::NearbyListSwapMoveSelector(c) => {
195                Self::push_nearby_swap(out, ctx, c.max_nearby);
196            }
197            MoveSelectorConfig::ListReverseMoveSelector(_) => {
198                Self::push_list_reverse(out, ctx);
199            }
200            MoveSelectorConfig::SubListChangeMoveSelector(c) => {
201                Self::push_sublist_change(out, ctx, c.min_sublist_size, c.max_sublist_size);
202            }
203            MoveSelectorConfig::SubListSwapMoveSelector(c) => {
204                Self::push_sublist_swap(out, ctx, c.min_sublist_size, c.max_sublist_size);
205            }
206            MoveSelectorConfig::KOptMoveSelector(c) => {
207                Self::push_kopt(out, ctx, c.k, c.min_segment_len, c.max_nearby);
208            }
209            MoveSelectorConfig::ListRuinMoveSelector(c) => {
210                Self::push_list_ruin(out, ctx, c.min_ruin_count, c.max_ruin_count);
211            }
212            MoveSelectorConfig::ListChangeMoveSelector(_) => {
213                Self::push_list_change(out, ctx);
214            }
215            MoveSelectorConfig::ListSwapMoveSelector(_) => {
216                Self::push_list_swap(out, ctx);
217            }
218            MoveSelectorConfig::UnionMoveSelector(u) => {
219                for child in &u.selectors {
220                    Self::collect_leaves(child, ctx, out);
221                }
222            }
223            MoveSelectorConfig::ChangeMoveSelector(_) | MoveSelectorConfig::SwapMoveSelector(_) => {
224                panic!("standard move selector configured against a list-variable stock context");
225            }
226            MoveSelectorConfig::CartesianProductMoveSelector(_) => {
227                panic!("cartesian_product move selectors are not supported in stock solving");
228            }
229        }
230    }
231
232    fn push_nearby_change<S, V, DM, IDM>(
233        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
234        ctx: &ListContext<S, V, DM, IDM>,
235        max_nearby: usize,
236    ) where
237        S: PlanningSolution,
238        V: Clone + PartialEq + Send + Sync + Debug + 'static,
239        DM: CrossEntityDistanceMeter<S> + Clone,
240        IDM: CrossEntityDistanceMeter<S> + Clone,
241    {
242        use crate::heuristic::selector::nearby_list_change::NearbyListChangeMoveSelector;
243
244        let inner = NearbyListChangeMoveSelector::new(
245            FromSolutionEntitySelector::new(ctx.descriptor_index),
246            ctx.cross_distance_meter.clone(),
247            max_nearby,
248            ctx.list_len,
249            ctx.list_remove,
250            ctx.list_insert,
251            ctx.variable_name,
252            ctx.descriptor_index,
253        );
254        out.push(ListLeafSelector::NearbyListChange(
255            ListMoveNearbyListChangeSelector::new(inner),
256        ));
257    }
258
259    fn push_nearby_swap<S, V, DM, IDM>(
260        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
261        ctx: &ListContext<S, V, DM, IDM>,
262        max_nearby: usize,
263    ) where
264        S: PlanningSolution,
265        V: Clone + PartialEq + Send + Sync + Debug + 'static,
266        DM: CrossEntityDistanceMeter<S> + Clone,
267        IDM: CrossEntityDistanceMeter<S> + Clone,
268    {
269        use crate::heuristic::selector::nearby_list_swap::NearbyListSwapMoveSelector;
270
271        let inner = NearbyListSwapMoveSelector::new(
272            FromSolutionEntitySelector::new(ctx.descriptor_index),
273            ctx.intra_distance_meter.clone(),
274            max_nearby,
275            ctx.list_len,
276            ctx.list_get,
277            ctx.list_set,
278            ctx.variable_name,
279            ctx.descriptor_index,
280        );
281        out.push(ListLeafSelector::NearbyListSwap(
282            ListMoveNearbyListSwapSelector::new(inner),
283        ));
284    }
285
286    fn push_list_reverse<S, V, DM, IDM>(
287        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
288        ctx: &ListContext<S, V, DM, IDM>,
289    ) where
290        S: PlanningSolution,
291        V: Clone + PartialEq + Send + Sync + Debug + 'static,
292        DM: CrossEntityDistanceMeter<S> + Clone,
293        IDM: CrossEntityDistanceMeter<S> + Clone,
294    {
295        use crate::heuristic::selector::list_reverse::ListReverseMoveSelector;
296
297        let inner = ListReverseMoveSelector::new(
298            FromSolutionEntitySelector::new(ctx.descriptor_index),
299            ctx.list_len,
300            ctx.list_reverse,
301            ctx.variable_name,
302            ctx.descriptor_index,
303        );
304        out.push(ListLeafSelector::ListReverse(
305            ListMoveListReverseSelector::new(inner),
306        ));
307    }
308
309    fn push_sublist_change<S, V, DM, IDM>(
310        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
311        ctx: &ListContext<S, V, DM, IDM>,
312        min_sublist_size: usize,
313        max_sublist_size: usize,
314    ) where
315        S: PlanningSolution,
316        V: Clone + PartialEq + Send + Sync + Debug + 'static,
317        DM: CrossEntityDistanceMeter<S> + Clone,
318        IDM: CrossEntityDistanceMeter<S> + Clone,
319    {
320        use crate::heuristic::selector::sublist_change::SubListChangeMoveSelector;
321
322        let inner = SubListChangeMoveSelector::new(
323            FromSolutionEntitySelector::new(ctx.descriptor_index),
324            min_sublist_size,
325            max_sublist_size,
326            ctx.list_len,
327            ctx.sublist_remove,
328            ctx.sublist_insert,
329            ctx.variable_name,
330            ctx.descriptor_index,
331        );
332        out.push(ListLeafSelector::SubListChange(
333            ListMoveSubListChangeSelector::new(inner),
334        ));
335    }
336
337    fn push_sublist_swap<S, V, DM, IDM>(
338        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
339        ctx: &ListContext<S, V, DM, IDM>,
340        min_sublist_size: usize,
341        max_sublist_size: usize,
342    ) where
343        S: PlanningSolution,
344        V: Clone + PartialEq + Send + Sync + Debug + 'static,
345        DM: CrossEntityDistanceMeter<S> + Clone,
346        IDM: CrossEntityDistanceMeter<S> + Clone,
347    {
348        use crate::heuristic::selector::sublist_swap::SubListSwapMoveSelector;
349
350        let inner = SubListSwapMoveSelector::new(
351            FromSolutionEntitySelector::new(ctx.descriptor_index),
352            min_sublist_size,
353            max_sublist_size,
354            ctx.list_len,
355            ctx.sublist_remove,
356            ctx.sublist_insert,
357            ctx.variable_name,
358            ctx.descriptor_index,
359        );
360        out.push(ListLeafSelector::SubListSwap(
361            ListMoveSubListSwapSelector::new(inner),
362        ));
363    }
364
365    fn push_kopt<S, V, DM, IDM>(
366        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
367        ctx: &ListContext<S, V, DM, IDM>,
368        k: usize,
369        min_segment_len: usize,
370        max_nearby: usize,
371    ) where
372        S: PlanningSolution,
373        V: Clone + PartialEq + Send + Sync + Debug + 'static,
374        DM: CrossEntityDistanceMeter<S> + Clone,
375        IDM: CrossEntityDistanceMeter<S> + Clone,
376    {
377        use crate::heuristic::selector::k_opt::{KOptMoveSelector, NearbyKOptMoveSelector};
378
379        let config = KOptConfig::new(k.clamp(2, 5)).with_min_segment_len(min_segment_len);
380        if max_nearby > 0 {
381            let adapter = IntraDistanceAdapter(ctx.intra_distance_meter.clone());
382            let inner = NearbyKOptMoveSelector::new(
383                FromSolutionEntitySelector::new(ctx.descriptor_index),
384                adapter,
385                max_nearby,
386                config,
387                ctx.list_len,
388                ctx.sublist_remove,
389                ctx.sublist_insert,
390                ctx.variable_name,
391                ctx.descriptor_index,
392            );
393            out.push(ListLeafSelector::NearbyKOpt(
394                ListMoveNearbyKOptSelector::new(inner),
395            ));
396        } else {
397            let inner = KOptMoveSelector::new(
398                FromSolutionEntitySelector::new(ctx.descriptor_index),
399                config,
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::KOpt(ListMoveKOptSelector::new(inner)));
407        }
408    }
409
410    fn push_list_ruin<S, V, DM, IDM>(
411        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
412        ctx: &ListContext<S, V, DM, IDM>,
413        min_ruin_count: usize,
414        max_ruin_count: usize,
415    ) where
416        S: PlanningSolution,
417        V: Clone + PartialEq + Send + Sync + Debug + 'static,
418        DM: CrossEntityDistanceMeter<S> + Clone,
419        IDM: CrossEntityDistanceMeter<S> + Clone,
420    {
421        use crate::heuristic::selector::list_ruin::ListRuinMoveSelector;
422
423        let inner = ListRuinMoveSelector::new(
424            min_ruin_count.max(1),
425            max_ruin_count.max(1),
426            ctx.entity_count,
427            ctx.list_len,
428            ctx.ruin_remove,
429            ctx.ruin_insert,
430            ctx.variable_name,
431            ctx.descriptor_index,
432        );
433        out.push(ListLeafSelector::ListRuin(ListMoveListRuinSelector::new(
434            inner,
435        )));
436    }
437
438    fn push_list_change<S, V, DM, IDM>(
439        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
440        ctx: &ListContext<S, V, DM, IDM>,
441    ) where
442        S: PlanningSolution,
443        V: Clone + PartialEq + Send + Sync + Debug + 'static,
444        DM: CrossEntityDistanceMeter<S> + Clone,
445        IDM: CrossEntityDistanceMeter<S> + Clone,
446    {
447        use crate::heuristic::selector::list_change::ListChangeMoveSelector;
448
449        let inner = ListChangeMoveSelector::new(
450            FromSolutionEntitySelector::new(ctx.descriptor_index),
451            ctx.list_len,
452            ctx.list_remove,
453            ctx.list_insert,
454            ctx.variable_name,
455            ctx.descriptor_index,
456        );
457        out.push(ListLeafSelector::ListChange(
458            ListMoveListChangeSelector::new(inner),
459        ));
460    }
461
462    fn push_list_swap<S, V, DM, IDM>(
463        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
464        ctx: &ListContext<S, V, DM, IDM>,
465    ) where
466        S: PlanningSolution,
467        V: Clone + PartialEq + Send + Sync + Debug + 'static,
468        DM: CrossEntityDistanceMeter<S> + Clone,
469        IDM: CrossEntityDistanceMeter<S> + Clone,
470    {
471        use crate::heuristic::selector::list_swap::ListSwapMoveSelector;
472
473        let inner = ListSwapMoveSelector::new(
474            FromSolutionEntitySelector::new(ctx.descriptor_index),
475            ctx.list_len,
476            ctx.list_get,
477            ctx.list_set,
478            ctx.variable_name,
479            ctx.descriptor_index,
480        );
481        out.push(ListLeafSelector::ListSwap(ListMoveListSwapSelector::new(
482            inner,
483        )));
484    }
485}
solverforge_solver/builder/list_selector.rs

solverforge_solver/builder/
list_selector.rs
