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, MoveSelector,
15};
16use crate::heuristic::selector::{
17    FromSolutionEntitySelector, ListMoveListReverseSelector, ListMoveListSwapSelector,
18    ListMoveNearbyListChangeSelector, ListMoveNearbyListSwapSelector,
19    ListMoveSubListChangeSelector, ListMoveSubListSwapSelector,
20};
21
22use super::context::ListContext;
23
24/// A monomorphized leaf selector for list planning variables.
25///
26/// Each variant wraps one of the available list move selector wrapper types.
27/// Allows `VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>` to have
28/// a single concrete type regardless of configuration.
29pub enum ListLeafSelector<S, V, DM, IDM>
30where
31    S: PlanningSolution,
32    V: Clone + PartialEq + Send + Sync + Debug + 'static,
33    DM: CrossEntityDistanceMeter<S>,
34    IDM: CrossEntityDistanceMeter<S>,
35{
36    /// Nearby list change (distance-pruned relocation).
37    NearbyListChange(ListMoveNearbyListChangeSelector<S, V, DM, FromSolutionEntitySelector>),
38    /// Nearby list swap (distance-pruned swap).
39    NearbyListSwap(ListMoveNearbyListSwapSelector<S, V, IDM, FromSolutionEntitySelector>),
40    /// List reverse (2-opt).
41    ListReverse(ListMoveListReverseSelector<S, V, FromSolutionEntitySelector>),
42    /// Sublist change (Or-opt).
43    SubListChange(ListMoveSubListChangeSelector<S, V, FromSolutionEntitySelector>),
44    /// K-opt.
45    KOpt(ListMoveKOptSelector<S, V, FromSolutionEntitySelector>),
46    /// List ruin (LNS).
47    ListRuin(ListMoveListRuinSelector<S, V>),
48    /// Full list change (unrestricted relocation).
49    ListChange(ListMoveListChangeSelector<S, V, FromSolutionEntitySelector>),
50    /// Full list swap (unrestricted swap).
51    ListSwap(ListMoveListSwapSelector<S, V, FromSolutionEntitySelector>),
52    /// Sublist swap.
53    SubListSwap(ListMoveSubListSwapSelector<S, V, FromSolutionEntitySelector>),
54}
55
56impl<S, V, DM, IDM> Debug for ListLeafSelector<S, V, DM, IDM>
57where
58    S: PlanningSolution,
59    V: Clone + PartialEq + Send + Sync + Debug + 'static,
60    DM: CrossEntityDistanceMeter<S>,
61    IDM: CrossEntityDistanceMeter<S>,
62{
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        match self {
65            Self::NearbyListChange(s) => write!(f, "ListLeafSelector::NearbyListChange({s:?})"),
66            Self::NearbyListSwap(s) => write!(f, "ListLeafSelector::NearbyListSwap({s:?})"),
67            Self::ListReverse(s) => write!(f, "ListLeafSelector::ListReverse({s:?})"),
68            Self::SubListChange(s) => write!(f, "ListLeafSelector::SubListChange({s:?})"),
69            Self::KOpt(s) => write!(f, "ListLeafSelector::KOpt({s:?})"),
70            Self::ListRuin(s) => write!(f, "ListLeafSelector::ListRuin({s:?})"),
71            Self::ListChange(s) => write!(f, "ListLeafSelector::ListChange({s:?})"),
72            Self::ListSwap(s) => write!(f, "ListLeafSelector::ListSwap({s:?})"),
73            Self::SubListSwap(s) => write!(f, "ListLeafSelector::SubListSwap({s:?})"),
74        }
75    }
76}
77
78impl<S, V, DM, IDM> MoveSelector<S, ListMoveImpl<S, V>> for ListLeafSelector<S, V, DM, IDM>
79where
80    S: PlanningSolution,
81    V: Clone + PartialEq + Send + Sync + Debug + 'static,
82    DM: CrossEntityDistanceMeter<S>,
83    IDM: CrossEntityDistanceMeter<S>,
84{
85    fn iter_moves<'a, D: Director<S>>(
86        &'a self,
87        score_director: &'a D,
88    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
89        let moves: Vec<ListMoveImpl<S, V>> = match self {
90            Self::NearbyListChange(s) => s.iter_moves(score_director).collect(),
91            Self::NearbyListSwap(s) => s.iter_moves(score_director).collect(),
92            Self::ListReverse(s) => s.iter_moves(score_director).collect(),
93            Self::SubListChange(s) => s.iter_moves(score_director).collect(),
94            Self::KOpt(s) => s.iter_moves(score_director).collect(),
95            Self::ListRuin(s) => s.iter_moves(score_director).collect(),
96            Self::ListChange(s) => s.iter_moves(score_director).collect(),
97            Self::ListSwap(s) => s.iter_moves(score_director).collect(),
98            Self::SubListSwap(s) => s.iter_moves(score_director).collect(),
99        };
100        moves.into_iter()
101    }
102
103    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
104        match self {
105            Self::NearbyListChange(s) => s.size(score_director),
106            Self::NearbyListSwap(s) => s.size(score_director),
107            Self::ListReverse(s) => s.size(score_director),
108            Self::SubListChange(s) => s.size(score_director),
109            Self::KOpt(s) => s.size(score_director),
110            Self::ListRuin(s) => s.size(score_director),
111            Self::ListChange(s) => s.size(score_director),
112            Self::ListSwap(s) => s.size(score_director),
113            Self::SubListSwap(s) => s.size(score_director),
114        }
115    }
116}
117
118/// Builder that constructs a `VecUnionSelector` of `ListLeafSelector` from config.
119pub struct ListMoveSelectorBuilder;
120
121impl ListMoveSelectorBuilder {
122    /// Builds a `VecUnionSelector` from move selector config and domain context.
123    ///
124    /// Default (no config): `Union(NearbyListChange(20), NearbyListSwap(20), ListReverse)`
125    pub fn build<S, V, DM, IDM>(
126        config: Option<&MoveSelectorConfig>,
127        ctx: &ListContext<S, V, DM, IDM>,
128    ) -> VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>
129    where
130        S: PlanningSolution,
131        V: Clone + PartialEq + Send + Sync + Debug + 'static,
132        DM: CrossEntityDistanceMeter<S> + Clone,
133        IDM: CrossEntityDistanceMeter<S> + Clone,
134    {
135        let mut leaves: Vec<ListLeafSelector<S, V, DM, IDM>> = Vec::new();
136        match config {
137            None => {
138                Self::push_nearby_change(&mut leaves, ctx, 20);
139                Self::push_nearby_swap(&mut leaves, ctx, 20);
140                Self::push_list_reverse(&mut leaves, ctx);
141            }
142            Some(cfg) => Self::collect_leaves(cfg, ctx, &mut leaves),
143        }
144        VecUnionSelector::new(leaves)
145    }
146
147    fn collect_leaves<S, V, DM, IDM>(
148        config: &MoveSelectorConfig,
149        ctx: &ListContext<S, V, DM, IDM>,
150        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
151    ) where
152        S: PlanningSolution,
153        V: Clone + PartialEq + Send + Sync + Debug + 'static,
154        DM: CrossEntityDistanceMeter<S> + Clone,
155        IDM: CrossEntityDistanceMeter<S> + Clone,
156    {
157        match config {
158            MoveSelectorConfig::NearbyListChangeMoveSelector(c) => {
159                Self::push_nearby_change(out, ctx, c.max_nearby);
160            }
161            MoveSelectorConfig::NearbyListSwapMoveSelector(c) => {
162                Self::push_nearby_swap(out, ctx, c.max_nearby);
163            }
164            MoveSelectorConfig::ListReverseMoveSelector(_) => {
165                Self::push_list_reverse(out, ctx);
166            }
167            MoveSelectorConfig::SubListChangeMoveSelector(c) => {
168                Self::push_sublist_change(out, ctx, c.min_sublist_size, c.max_sublist_size);
169            }
170            MoveSelectorConfig::SubListSwapMoveSelector(c) => {
171                Self::push_sublist_swap(out, ctx, c.min_sublist_size, c.max_sublist_size);
172            }
173            MoveSelectorConfig::KOptMoveSelector(c) => {
174                Self::push_kopt(out, ctx, c.k, c.min_segment_len);
175            }
176            MoveSelectorConfig::ListRuinMoveSelector(c) => {
177                Self::push_list_ruin(out, ctx, c.min_ruin_count, c.max_ruin_count);
178            }
179            MoveSelectorConfig::ListChangeMoveSelector(_) => {
180                Self::push_list_change(out, ctx);
181            }
182            MoveSelectorConfig::ListSwapMoveSelector(_) => {
183                Self::push_list_swap(out, ctx);
184            }
185            MoveSelectorConfig::UnionMoveSelector(u) => {
186                for child in &u.selectors {
187                    Self::collect_leaves(child, ctx, out);
188                }
189            }
190            // Basic variable selectors — ignore for list solver
191            _ => {}
192        }
193    }
194
195    fn push_nearby_change<S, V, DM, IDM>(
196        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
197        ctx: &ListContext<S, V, DM, IDM>,
198        max_nearby: usize,
199    ) where
200        S: PlanningSolution,
201        V: Clone + PartialEq + Send + Sync + Debug + 'static,
202        DM: CrossEntityDistanceMeter<S> + Clone,
203        IDM: CrossEntityDistanceMeter<S> + Clone,
204    {
205        use crate::heuristic::selector::nearby_list_change::NearbyListChangeMoveSelector;
206
207        let inner = NearbyListChangeMoveSelector::new(
208            FromSolutionEntitySelector::new(ctx.descriptor_index),
209            ctx.cross_distance_meter.clone(),
210            max_nearby,
211            ctx.list_len,
212            ctx.list_remove,
213            ctx.list_insert,
214            ctx.variable_name,
215            ctx.descriptor_index,
216        );
217        out.push(ListLeafSelector::NearbyListChange(
218            ListMoveNearbyListChangeSelector::new(inner),
219        ));
220    }
221
222    fn push_nearby_swap<S, V, DM, IDM>(
223        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
224        ctx: &ListContext<S, V, DM, IDM>,
225        max_nearby: usize,
226    ) where
227        S: PlanningSolution,
228        V: Clone + PartialEq + Send + Sync + Debug + 'static,
229        DM: CrossEntityDistanceMeter<S> + Clone,
230        IDM: CrossEntityDistanceMeter<S> + Clone,
231    {
232        use crate::heuristic::selector::nearby_list_swap::NearbyListSwapMoveSelector;
233
234        let inner = NearbyListSwapMoveSelector::new(
235            FromSolutionEntitySelector::new(ctx.descriptor_index),
236            ctx.intra_distance_meter.clone(),
237            max_nearby,
238            ctx.list_len,
239            ctx.list_get,
240            ctx.list_set,
241            ctx.variable_name,
242            ctx.descriptor_index,
243        );
244        out.push(ListLeafSelector::NearbyListSwap(
245            ListMoveNearbyListSwapSelector::new(inner),
246        ));
247    }
248
249    fn push_list_reverse<S, V, DM, IDM>(
250        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
251        ctx: &ListContext<S, V, DM, IDM>,
252    ) where
253        S: PlanningSolution,
254        V: Clone + PartialEq + Send + Sync + Debug + 'static,
255        DM: CrossEntityDistanceMeter<S> + Clone,
256        IDM: CrossEntityDistanceMeter<S> + Clone,
257    {
258        use crate::heuristic::selector::list_reverse::ListReverseMoveSelector;
259
260        let inner = ListReverseMoveSelector::new(
261            FromSolutionEntitySelector::new(ctx.descriptor_index),
262            ctx.list_len,
263            ctx.list_reverse,
264            ctx.variable_name,
265            ctx.descriptor_index,
266        );
267        out.push(ListLeafSelector::ListReverse(
268            ListMoveListReverseSelector::new(inner),
269        ));
270    }
271
272    fn push_sublist_change<S, V, DM, IDM>(
273        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
274        ctx: &ListContext<S, V, DM, IDM>,
275        min_sublist_size: usize,
276        max_sublist_size: usize,
277    ) where
278        S: PlanningSolution,
279        V: Clone + PartialEq + Send + Sync + Debug + 'static,
280        DM: CrossEntityDistanceMeter<S> + Clone,
281        IDM: CrossEntityDistanceMeter<S> + Clone,
282    {
283        use crate::heuristic::selector::sublist_change::SubListChangeMoveSelector;
284
285        let inner = SubListChangeMoveSelector::new(
286            FromSolutionEntitySelector::new(ctx.descriptor_index),
287            min_sublist_size,
288            max_sublist_size,
289            ctx.list_len,
290            ctx.sublist_remove,
291            ctx.sublist_insert,
292            ctx.variable_name,
293            ctx.descriptor_index,
294        );
295        out.push(ListLeafSelector::SubListChange(
296            ListMoveSubListChangeSelector::new(inner),
297        ));
298    }
299
300    fn push_sublist_swap<S, V, DM, IDM>(
301        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
302        ctx: &ListContext<S, V, DM, IDM>,
303        min_sublist_size: usize,
304        max_sublist_size: usize,
305    ) where
306        S: PlanningSolution,
307        V: Clone + PartialEq + Send + Sync + Debug + 'static,
308        DM: CrossEntityDistanceMeter<S> + Clone,
309        IDM: CrossEntityDistanceMeter<S> + Clone,
310    {
311        use crate::heuristic::selector::sublist_swap::SubListSwapMoveSelector;
312
313        let inner = SubListSwapMoveSelector::new(
314            FromSolutionEntitySelector::new(ctx.descriptor_index),
315            min_sublist_size,
316            max_sublist_size,
317            ctx.list_len,
318            ctx.sublist_remove,
319            ctx.sublist_insert,
320            ctx.variable_name,
321            ctx.descriptor_index,
322        );
323        out.push(ListLeafSelector::SubListSwap(
324            ListMoveSubListSwapSelector::new(inner),
325        ));
326    }
327
328    fn push_kopt<S, V, DM, IDM>(
329        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
330        ctx: &ListContext<S, V, DM, IDM>,
331        k: usize,
332        min_segment_len: usize,
333    ) where
334        S: PlanningSolution,
335        V: Clone + PartialEq + Send + Sync + Debug + 'static,
336        DM: CrossEntityDistanceMeter<S> + Clone,
337        IDM: CrossEntityDistanceMeter<S> + Clone,
338    {
339        use crate::heuristic::selector::k_opt::KOptMoveSelector;
340
341        let config = KOptConfig::new(k.clamp(2, 5)).with_min_segment_len(min_segment_len);
342        let inner = KOptMoveSelector::new(
343            FromSolutionEntitySelector::new(ctx.descriptor_index),
344            config,
345            ctx.list_len,
346            ctx.sublist_remove,
347            ctx.sublist_insert,
348            ctx.variable_name,
349            ctx.descriptor_index,
350        );
351        out.push(ListLeafSelector::KOpt(ListMoveKOptSelector::new(inner)));
352    }
353
354    fn push_list_ruin<S, V, DM, IDM>(
355        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
356        ctx: &ListContext<S, V, DM, IDM>,
357        min_ruin_count: usize,
358        max_ruin_count: usize,
359    ) where
360        S: PlanningSolution,
361        V: Clone + PartialEq + Send + Sync + Debug + 'static,
362        DM: CrossEntityDistanceMeter<S> + Clone,
363        IDM: CrossEntityDistanceMeter<S> + Clone,
364    {
365        use crate::heuristic::selector::list_ruin::ListRuinMoveSelector;
366
367        let inner = ListRuinMoveSelector::new(
368            min_ruin_count.max(1),
369            max_ruin_count.max(1),
370            ctx.entity_count,
371            ctx.list_len,
372            ctx.ruin_remove,
373            ctx.ruin_insert,
374            ctx.variable_name,
375            ctx.descriptor_index,
376        );
377        out.push(ListLeafSelector::ListRuin(ListMoveListRuinSelector::new(
378            inner,
379        )));
380    }
381
382    fn push_list_change<S, V, DM, IDM>(
383        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
384        ctx: &ListContext<S, V, DM, IDM>,
385    ) where
386        S: PlanningSolution,
387        V: Clone + PartialEq + Send + Sync + Debug + 'static,
388        DM: CrossEntityDistanceMeter<S> + Clone,
389        IDM: CrossEntityDistanceMeter<S> + Clone,
390    {
391        use crate::heuristic::selector::list_change::ListChangeMoveSelector;
392
393        let inner = ListChangeMoveSelector::new(
394            FromSolutionEntitySelector::new(ctx.descriptor_index),
395            ctx.list_len,
396            ctx.list_remove,
397            ctx.list_insert,
398            ctx.variable_name,
399            ctx.descriptor_index,
400        );
401        out.push(ListLeafSelector::ListChange(
402            ListMoveListChangeSelector::new(inner),
403        ));
404    }
405
406    fn push_list_swap<S, V, DM, IDM>(
407        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
408        ctx: &ListContext<S, V, DM, IDM>,
409    ) where
410        S: PlanningSolution,
411        V: Clone + PartialEq + Send + Sync + Debug + 'static,
412        DM: CrossEntityDistanceMeter<S> + Clone,
413        IDM: CrossEntityDistanceMeter<S> + Clone,
414    {
415        use crate::heuristic::selector::list_swap::ListSwapMoveSelector;
416
417        let inner = ListSwapMoveSelector::new(
418            FromSolutionEntitySelector::new(ctx.descriptor_index),
419            ctx.list_len,
420            ctx.list_get,
421            ctx.list_set,
422            ctx.variable_name,
423            ctx.descriptor_index,
424        );
425        out.push(ListLeafSelector::ListSwap(ListMoveListSwapSelector::new(
426            inner,
427        )));
428    }
429}
solverforge_solver/builder/list_selector.rs

solverforge_solver/builder/
list_selector.rs
