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;
10use crate::heuristic::selector::decorator::VecUnionSelector;
11use crate::heuristic::selector::k_opt::KOptConfig;
12use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
13use crate::heuristic::selector::typed_move_selector::{
14    ListMoveKOptSelector, ListMoveListChangeSelector, ListMoveListRuinSelector,
15    ListMoveNearbyKOptSelector, MoveSelector,
16};
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
128/// Builder that constructs a `VecUnionSelector` of `ListLeafSelector` from config.
129pub struct ListMoveSelectorBuilder;
130
131impl ListMoveSelectorBuilder {
132    /// Builds a `VecUnionSelector` from move selector config and domain context.
133    ///
134    /// Default (no config): `Union(NearbyListChange(20), NearbyListSwap(20), ListReverse)`
135    pub fn build<S, V, DM, IDM>(
136        config: Option<&MoveSelectorConfig>,
137        ctx: &ListContext<S, V, DM, IDM>,
138    ) -> VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>
139    where
140        S: PlanningSolution,
141        V: Clone + PartialEq + Send + Sync + Debug + 'static,
142        DM: CrossEntityDistanceMeter<S> + Clone,
143        IDM: CrossEntityDistanceMeter<S> + Clone,
144    {
145        let mut leaves: Vec<ListLeafSelector<S, V, DM, IDM>> = Vec::new();
146        match config {
147            None => {
148                Self::push_nearby_change(&mut leaves, ctx, 20);
149                Self::push_nearby_swap(&mut leaves, ctx, 20);
150                Self::push_list_reverse(&mut leaves, ctx);
151            }
152            Some(cfg) => Self::collect_leaves(cfg, ctx, &mut leaves),
153        }
154        VecUnionSelector::new(leaves)
155    }
156
157    fn collect_leaves<S, V, DM, IDM>(
158        config: &MoveSelectorConfig,
159        ctx: &ListContext<S, V, DM, IDM>,
160        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
161    ) where
162        S: PlanningSolution,
163        V: Clone + PartialEq + Send + Sync + Debug + 'static,
164        DM: CrossEntityDistanceMeter<S> + Clone,
165        IDM: CrossEntityDistanceMeter<S> + Clone,
166    {
167        match config {
168            MoveSelectorConfig::NearbyListChangeMoveSelector(c) => {
169                Self::push_nearby_change(out, ctx, c.max_nearby);
170            }
171            MoveSelectorConfig::NearbyListSwapMoveSelector(c) => {
172                Self::push_nearby_swap(out, ctx, c.max_nearby);
173            }
174            MoveSelectorConfig::ListReverseMoveSelector(_) => {
175                Self::push_list_reverse(out, ctx);
176            }
177            MoveSelectorConfig::SubListChangeMoveSelector(c) => {
178                Self::push_sublist_change(out, ctx, c.min_sublist_size, c.max_sublist_size);
179            }
180            MoveSelectorConfig::SubListSwapMoveSelector(c) => {
181                Self::push_sublist_swap(out, ctx, c.min_sublist_size, c.max_sublist_size);
182            }
183            MoveSelectorConfig::KOptMoveSelector(c) => {
184                Self::push_kopt(out, ctx, c.k, c.min_segment_len, c.max_nearby);
185            }
186            MoveSelectorConfig::ListRuinMoveSelector(c) => {
187                Self::push_list_ruin(out, ctx, c.min_ruin_count, c.max_ruin_count);
188            }
189            MoveSelectorConfig::ListChangeMoveSelector(_) => {
190                Self::push_list_change(out, ctx);
191            }
192            MoveSelectorConfig::ListSwapMoveSelector(_) => {
193                Self::push_list_swap(out, ctx);
194            }
195            MoveSelectorConfig::UnionMoveSelector(u) => {
196                for child in &u.selectors {
197                    Self::collect_leaves(child, ctx, out);
198                }
199            }
200            // Basic variable selectors — ignore for list solver
201            _ => {}
202        }
203    }
204
205    fn push_nearby_change<S, V, DM, IDM>(
206        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
207        ctx: &ListContext<S, V, DM, IDM>,
208        max_nearby: usize,
209    ) where
210        S: PlanningSolution,
211        V: Clone + PartialEq + Send + Sync + Debug + 'static,
212        DM: CrossEntityDistanceMeter<S> + Clone,
213        IDM: CrossEntityDistanceMeter<S> + Clone,
214    {
215        use crate::heuristic::selector::nearby_list_change::NearbyListChangeMoveSelector;
216
217        let inner = NearbyListChangeMoveSelector::new(
218            FromSolutionEntitySelector::new(ctx.descriptor_index),
219            ctx.cross_distance_meter.clone(),
220            max_nearby,
221            ctx.list_len,
222            ctx.list_remove,
223            ctx.list_insert,
224            ctx.variable_name,
225            ctx.descriptor_index,
226        );
227        out.push(ListLeafSelector::NearbyListChange(
228            ListMoveNearbyListChangeSelector::new(inner),
229        ));
230    }
231
232    fn push_nearby_swap<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_swap::NearbyListSwapMoveSelector;
243
244        let inner = NearbyListSwapMoveSelector::new(
245            FromSolutionEntitySelector::new(ctx.descriptor_index),
246            ctx.intra_distance_meter.clone(),
247            max_nearby,
248            ctx.list_len,
249            ctx.list_get,
250            ctx.list_set,
251            ctx.variable_name,
252            ctx.descriptor_index,
253        );
254        out.push(ListLeafSelector::NearbyListSwap(
255            ListMoveNearbyListSwapSelector::new(inner),
256        ));
257    }
258
259    fn push_list_reverse<S, V, DM, IDM>(
260        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
261        ctx: &ListContext<S, V, DM, IDM>,
262    ) where
263        S: PlanningSolution,
264        V: Clone + PartialEq + Send + Sync + Debug + 'static,
265        DM: CrossEntityDistanceMeter<S> + Clone,
266        IDM: CrossEntityDistanceMeter<S> + Clone,
267    {
268        use crate::heuristic::selector::list_reverse::ListReverseMoveSelector;
269
270        let inner = ListReverseMoveSelector::new(
271            FromSolutionEntitySelector::new(ctx.descriptor_index),
272            ctx.list_len,
273            ctx.list_reverse,
274            ctx.variable_name,
275            ctx.descriptor_index,
276        );
277        out.push(ListLeafSelector::ListReverse(
278            ListMoveListReverseSelector::new(inner),
279        ));
280    }
281
282    fn push_sublist_change<S, V, DM, IDM>(
283        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
284        ctx: &ListContext<S, V, DM, IDM>,
285        min_sublist_size: usize,
286        max_sublist_size: usize,
287    ) where
288        S: PlanningSolution,
289        V: Clone + PartialEq + Send + Sync + Debug + 'static,
290        DM: CrossEntityDistanceMeter<S> + Clone,
291        IDM: CrossEntityDistanceMeter<S> + Clone,
292    {
293        use crate::heuristic::selector::sublist_change::SubListChangeMoveSelector;
294
295        let inner = SubListChangeMoveSelector::new(
296            FromSolutionEntitySelector::new(ctx.descriptor_index),
297            min_sublist_size,
298            max_sublist_size,
299            ctx.list_len,
300            ctx.sublist_remove,
301            ctx.sublist_insert,
302            ctx.variable_name,
303            ctx.descriptor_index,
304        );
305        out.push(ListLeafSelector::SubListChange(
306            ListMoveSubListChangeSelector::new(inner),
307        ));
308    }
309
310    fn push_sublist_swap<S, V, DM, IDM>(
311        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
312        ctx: &ListContext<S, V, DM, IDM>,
313        min_sublist_size: usize,
314        max_sublist_size: usize,
315    ) where
316        S: PlanningSolution,
317        V: Clone + PartialEq + Send + Sync + Debug + 'static,
318        DM: CrossEntityDistanceMeter<S> + Clone,
319        IDM: CrossEntityDistanceMeter<S> + Clone,
320    {
321        use crate::heuristic::selector::sublist_swap::SubListSwapMoveSelector;
322
323        let inner = SubListSwapMoveSelector::new(
324            FromSolutionEntitySelector::new(ctx.descriptor_index),
325            min_sublist_size,
326            max_sublist_size,
327            ctx.list_len,
328            ctx.sublist_remove,
329            ctx.sublist_insert,
330            ctx.variable_name,
331            ctx.descriptor_index,
332        );
333        out.push(ListLeafSelector::SubListSwap(
334            ListMoveSubListSwapSelector::new(inner),
335        ));
336    }
337
338    fn push_kopt<S, V, DM, IDM>(
339        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
340        ctx: &ListContext<S, V, DM, IDM>,
341        k: usize,
342        min_segment_len: usize,
343        max_nearby: usize,
344    ) where
345        S: PlanningSolution,
346        V: Clone + PartialEq + Send + Sync + Debug + 'static,
347        DM: CrossEntityDistanceMeter<S> + Clone,
348        IDM: CrossEntityDistanceMeter<S> + Clone,
349    {
350        use crate::heuristic::selector::k_opt::{KOptMoveSelector, NearbyKOptMoveSelector};
351
352        let config = KOptConfig::new(k.clamp(2, 5)).with_min_segment_len(min_segment_len);
353        if max_nearby > 0 {
354            let adapter = IntraDistanceAdapter(ctx.intra_distance_meter.clone());
355            let inner = NearbyKOptMoveSelector::new(
356                FromSolutionEntitySelector::new(ctx.descriptor_index),
357                adapter,
358                max_nearby,
359                config,
360                ctx.list_len,
361                ctx.sublist_remove,
362                ctx.sublist_insert,
363                ctx.variable_name,
364                ctx.descriptor_index,
365            );
366            out.push(ListLeafSelector::NearbyKOpt(
367                ListMoveNearbyKOptSelector::new(inner),
368            ));
369        } else {
370            let inner = KOptMoveSelector::new(
371                FromSolutionEntitySelector::new(ctx.descriptor_index),
372                config,
373                ctx.list_len,
374                ctx.sublist_remove,
375                ctx.sublist_insert,
376                ctx.variable_name,
377                ctx.descriptor_index,
378            );
379            out.push(ListLeafSelector::KOpt(ListMoveKOptSelector::new(inner)));
380        }
381    }
382
383    fn push_list_ruin<S, V, DM, IDM>(
384        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
385        ctx: &ListContext<S, V, DM, IDM>,
386        min_ruin_count: usize,
387        max_ruin_count: 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::list_ruin::ListRuinMoveSelector;
395
396        let inner = ListRuinMoveSelector::new(
397            min_ruin_count.max(1),
398            max_ruin_count.max(1),
399            ctx.entity_count,
400            ctx.list_len,
401            ctx.ruin_remove,
402            ctx.ruin_insert,
403            ctx.variable_name,
404            ctx.descriptor_index,
405        );
406        out.push(ListLeafSelector::ListRuin(ListMoveListRuinSelector::new(
407            inner,
408        )));
409    }
410
411    fn push_list_change<S, V, DM, IDM>(
412        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
413        ctx: &ListContext<S, V, DM, IDM>,
414    ) where
415        S: PlanningSolution,
416        V: Clone + PartialEq + Send + Sync + Debug + 'static,
417        DM: CrossEntityDistanceMeter<S> + Clone,
418        IDM: CrossEntityDistanceMeter<S> + Clone,
419    {
420        use crate::heuristic::selector::list_change::ListChangeMoveSelector;
421
422        let inner = ListChangeMoveSelector::new(
423            FromSolutionEntitySelector::new(ctx.descriptor_index),
424            ctx.list_len,
425            ctx.list_remove,
426            ctx.list_insert,
427            ctx.variable_name,
428            ctx.descriptor_index,
429        );
430        out.push(ListLeafSelector::ListChange(
431            ListMoveListChangeSelector::new(inner),
432        ));
433    }
434
435    fn push_list_swap<S, V, DM, IDM>(
436        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
437        ctx: &ListContext<S, V, DM, IDM>,
438    ) where
439        S: PlanningSolution,
440        V: Clone + PartialEq + Send + Sync + Debug + 'static,
441        DM: CrossEntityDistanceMeter<S> + Clone,
442        IDM: CrossEntityDistanceMeter<S> + Clone,
443    {
444        use crate::heuristic::selector::list_swap::ListSwapMoveSelector;
445
446        let inner = ListSwapMoveSelector::new(
447            FromSolutionEntitySelector::new(ctx.descriptor_index),
448            ctx.list_len,
449            ctx.list_get,
450            ctx.list_set,
451            ctx.variable_name,
452            ctx.descriptor_index,
453        );
454        out.push(ListLeafSelector::ListSwap(ListMoveListSwapSelector::new(
455            inner,
456        )));
457    }
458}
solverforge_solver/builder/list_selector.rs

solverforge_solver/builder/
list_selector.rs
