solverforge_solver/builder/selector/
families.rs

1pub type Selector<S, V, DM, IDM> =
2    VecUnionSelector<S, NeighborhoodMove<S, V>, Neighborhood<S, V, DM, IDM>>;
3
4pub type LocalSearch<S, V, DM, IDM> = LocalSearchPhase<
5    S,
6    NeighborhoodMove<S, V>,
7    Selector<S, V, DM, IDM>,
8    AnyAcceptor<S>,
9    AnyForager<S>,
10>;
11
12pub struct LocalSearchStrategy<S, V, DM, IDM>
13where
14    S: PlanningSolution + 'static,
15    V: Clone + PartialEq + Send + Sync + Debug + 'static,
16    DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
17    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
18{
19    inner: LocalSearchStrategyInner<S, V, DM, IDM>,
20}
21
22#[allow(clippy::large_enum_variant)] // Inline storage keeps local-search phases zero-erasure.
23enum LocalSearchStrategyInner<S, V, DM, IDM>
24where
25    S: PlanningSolution + 'static,
26    V: Clone + PartialEq + Send + Sync + Debug + 'static,
27    DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
28    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
29{
30    AcceptorForager(LocalSearch<S, V, DM, IDM>),
31    VariableNeighborhoodDescent(VndPhase<S, NeighborhoodMove<S, V>, Neighborhood<S, V, DM, IDM>>),
32}
33
34impl<S, V, DM, IDM> LocalSearchStrategy<S, V, DM, IDM>
35where
36    S: PlanningSolution + 'static,
37    V: Clone + PartialEq + Send + Sync + Debug + 'static,
38    DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
39    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
40{
41    fn acceptor_forager(phase: LocalSearch<S, V, DM, IDM>) -> Self {
42        Self {
43            inner: LocalSearchStrategyInner::AcceptorForager(phase),
44        }
45    }
46
47    fn variable_neighborhood_descent(
48        phase: VndPhase<S, NeighborhoodMove<S, V>, Neighborhood<S, V, DM, IDM>>,
49    ) -> Self {
50        Self {
51            inner: LocalSearchStrategyInner::VariableNeighborhoodDescent(phase),
52        }
53    }
54}
55
56impl<S, V, DM, IDM> Debug for LocalSearchStrategy<S, V, DM, IDM>
57where
58    S: PlanningSolution + 'static,
59    V: Clone + PartialEq + Send + Sync + Debug + 'static,
60    DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
61    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
62{
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        match &self.inner {
65            LocalSearchStrategyInner::AcceptorForager(phase) => f
66                .debug_tuple("LocalSearchStrategy::AcceptorForager")
67                .field(phase)
68                .finish(),
69            LocalSearchStrategyInner::VariableNeighborhoodDescent(phase) => f
70                .debug_tuple("LocalSearchStrategy::VariableNeighborhoodDescent")
71                .field(phase)
72                .finish(),
73        }
74    }
75}
76
77impl<S, V, DM, IDM, D, ProgressCb> Phase<S, D, ProgressCb>
78    for LocalSearchStrategy<S, V, DM, IDM>
79where
80    S: PlanningSolution + 'static,
81    V: Clone + PartialEq + Send + Sync + Debug + 'static,
82    DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
83    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
84    D: solverforge_scoring::Director<S>,
85    ProgressCb: ProgressCallback<S>,
86{
87    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
88        match &mut self.inner {
89            LocalSearchStrategyInner::AcceptorForager(phase) => phase.solve(solver_scope),
90            LocalSearchStrategyInner::VariableNeighborhoodDescent(phase) => phase.solve(solver_scope),
91        }
92    }
93
94    fn phase_type_name(&self) -> &'static str {
95        "LocalSearch"
96    }
97}
98
99#[derive(Clone, Copy, Debug, PartialEq, Eq)]
100enum SelectorFamily {
101    Scalar,
102    List,
103    Mixed,
104    Unsupported,
105}
106
107fn selector_family(config: &MoveSelectorConfig) -> SelectorFamily {
108    match config {
109        MoveSelectorConfig::ChangeMoveSelector(_)
110        | MoveSelectorConfig::SwapMoveSelector(_)
111        | MoveSelectorConfig::NearbyChangeMoveSelector(_)
112        | MoveSelectorConfig::NearbySwapMoveSelector(_)
113        | MoveSelectorConfig::PillarChangeMoveSelector(_)
114        | MoveSelectorConfig::PillarSwapMoveSelector(_)
115        | MoveSelectorConfig::RuinRecreateMoveSelector(_)
116        | MoveSelectorConfig::GroupedScalarMoveSelector(_)
117        | MoveSelectorConfig::ConflictRepairMoveSelector(_)
118        | MoveSelectorConfig::CompoundConflictRepairMoveSelector(_) => SelectorFamily::Scalar,
119        MoveSelectorConfig::ListChangeMoveSelector(_)
120        | MoveSelectorConfig::NearbyListChangeMoveSelector(_)
121        | MoveSelectorConfig::ListSwapMoveSelector(_)
122        | MoveSelectorConfig::NearbyListSwapMoveSelector(_)
123        | MoveSelectorConfig::SublistChangeMoveSelector(_)
124        | MoveSelectorConfig::SublistSwapMoveSelector(_)
125        | MoveSelectorConfig::ListReverseMoveSelector(_)
126        | MoveSelectorConfig::KOptMoveSelector(_)
127        | MoveSelectorConfig::ListRuinMoveSelector(_) => SelectorFamily::List,
128        MoveSelectorConfig::LimitedNeighborhood(limit) => selector_family(limit.selector.as_ref()),
129        MoveSelectorConfig::UnionMoveSelector(union) => {
130            let mut family = None;
131            for child in &union.selectors {
132                let child_family = selector_family(child);
133                if child_family == SelectorFamily::Unsupported {
134                    return SelectorFamily::Unsupported;
135                }
136                family = Some(match family {
137                    None => child_family,
138                    Some(current) if current == child_family => current,
139                    Some(_) => SelectorFamily::Mixed,
140                });
141                if family == Some(SelectorFamily::Mixed) {
142                    return SelectorFamily::Mixed;
143                }
144            }
145            family.unwrap_or(SelectorFamily::Mixed)
146        }
147        MoveSelectorConfig::CartesianProductMoveSelector(_) => SelectorFamily::Unsupported,
148    }
149}
150
151fn selector_family_name(config: Option<&MoveSelectorConfig>) -> &'static str {
152    match config.map(selector_family) {
153        None => "default",
154        Some(SelectorFamily::Scalar) => "scalar",
155        Some(SelectorFamily::List) => "list",
156        Some(SelectorFamily::Mixed) => "mixed",
157        Some(SelectorFamily::Unsupported) => "unsupported",
158    }
159}
160
161fn selector_requires_score_during_move(config: &MoveSelectorConfig) -> bool {
162    match config {
163        MoveSelectorConfig::RuinRecreateMoveSelector(_)
164        | MoveSelectorConfig::ListRuinMoveSelector(_) => true,
165        MoveSelectorConfig::LimitedNeighborhood(limit) => {
166            selector_requires_score_during_move(limit.selector.as_ref())
167        }
168        MoveSelectorConfig::UnionMoveSelector(union) => union
169            .selectors
170            .iter()
171            .any(selector_requires_score_during_move),
172        MoveSelectorConfig::CartesianProductMoveSelector(_) => true,
173        _ => false,
174    }
175}
176
177fn assert_cartesian_left_preview_safe(config: &MoveSelectorConfig) {
178    assert!(
179        !selector_requires_score_during_move(config),
180        "cartesian_product left child cannot contain ruin_recreate_move_selector or list_ruin_move_selector because preview directors do not calculate scores",
181    );
182}
183
184fn push_scalar_selector<S, V, DM, IDM>(
185    config: Option<&MoveSelectorConfig>,
186    model: &RuntimeModel<S, V, DM, IDM>,
187    random_seed: Option<u64>,
188    out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
189) where
190    S: PlanningSolution + 'static,
191    V: Clone + PartialEq + Send + Sync + Debug + 'static,
192    DM: CrossEntityDistanceMeter<S> + Clone + 'static,
193    IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
194{
195    let scalar_variables: Vec<_> = model.scalar_variables().copied().collect();
196    if scalar_variables.is_empty() {
197        return;
198    }
199    if let Some(config) = config {
200        if let Some(variable) = assignment_owned_scalar_target(config, model) {
201            panic!(
202                "scalar move selector targets assignment-owned scalar variable {}.{}; use the owning grouped scalar assignment selector instead",
203                variable.entity_type_name,
204                variable.variable_name
205            );
206        }
207    }
208    let selector = build_scalar_flat_selector(config, &scalar_variables, random_seed);
209    out.extend(
210        selector
211            .into_selectors()
212            .into_iter()
213            .map(NeighborhoodLeaf::Scalar),
214    );
215}
216
217fn assignment_owned_scalar_target<S, V, DM, IDM>(
218    config: &MoveSelectorConfig,
219    model: &RuntimeModel<S, V, DM, IDM>,
220) -> Option<crate::builder::ScalarVariableSlot<S>> {
221    match config {
222        MoveSelectorConfig::ChangeMoveSelector(config) => {
223            target_assignment_owner(&config.target, model)
224        }
225        MoveSelectorConfig::SwapMoveSelector(config) => target_assignment_owner(&config.target, model),
226        MoveSelectorConfig::NearbyChangeMoveSelector(config) => {
227            target_assignment_owner(&config.target, model)
228        }
229        MoveSelectorConfig::NearbySwapMoveSelector(config) => {
230            target_assignment_owner(&config.target, model)
231        }
232        MoveSelectorConfig::PillarChangeMoveSelector(config) => {
233            target_assignment_owner(&config.target, model)
234        }
235        MoveSelectorConfig::PillarSwapMoveSelector(config) => {
236            target_assignment_owner(&config.target, model)
237        }
238        MoveSelectorConfig::RuinRecreateMoveSelector(config) => {
239            target_assignment_owner(&config.target, model)
240        }
241        MoveSelectorConfig::LimitedNeighborhood(limit) => {
242            assignment_owned_scalar_target(limit.selector.as_ref(), model)
243        }
244        MoveSelectorConfig::UnionMoveSelector(union) => union
245            .selectors
246            .iter()
247            .find_map(|selector| assignment_owned_scalar_target(selector, model)),
248        _ => None,
249    }
250}
251
252fn target_assignment_owner<S, V, DM, IDM>(
253    target: &solverforge_config::VariableTargetConfig,
254    model: &RuntimeModel<S, V, DM, IDM>,
255) -> Option<crate::builder::ScalarVariableSlot<S>> {
256    model.scalar_variables().copied().find(|variable| {
257        variable.matches_target(
258            target.entity_class.as_deref(),
259            target.variable_name.as_deref(),
260        ) && model.assignment_group_covers_scalar_variable(variable)
261    })
262}
263
264fn push_list_selector<S, V, DM, IDM>(
265    config: Option<&MoveSelectorConfig>,
266    model: &RuntimeModel<S, V, DM, IDM>,
267    random_seed: Option<u64>,
268    out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
269) where
270    S: PlanningSolution + 'static,
271    V: Clone + PartialEq + Send + Sync + Debug + 'static,
272    DM: CrossEntityDistanceMeter<S> + Clone + 'static,
273    IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
274{
275    for variable in model.list_variables() {
276        let selector = ListMoveSelectorBuilder::build_flat(config, variable, random_seed);
277        out.extend(
278            selector
279                .into_selectors()
280                .into_iter()
281                .map(NeighborhoodLeaf::List),
282        );
283    }
284}
285
286fn push_conflict_repair_selector<S, V, DM, IDM>(
287    config: &solverforge_config::ConflictRepairMoveSelectorConfig,
288    model: &RuntimeModel<S, V, DM, IDM>,
289    out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
290) where
291    S: PlanningSolution + 'static,
292    V: Clone + PartialEq + Send + Sync + Debug + 'static,
293    DM: CrossEntityDistanceMeter<S> + Clone + 'static,
294    IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
295{
296    if config.constraints.is_empty() {
297        panic!("conflict_repair_move_selector requires at least one constraint");
298    }
299    let scalar_variables = model
300        .scalar_variables()
301        .filter(|variable| !model.assignment_group_covers_scalar_variable(variable))
302        .copied()
303        .collect::<Vec<_>>();
304    let repairs = model
305        .conflict_repairs()
306        .iter()
307        .copied()
308        .filter(|repair| {
309            config
310                .constraints
311                .iter()
312                .any(|constraint| constraint == repair.constraint_name())
313        })
314        .collect::<Vec<_>>();
315    if repairs.is_empty() {
316        panic!(
317            "conflict_repair_move_selector configured for {:?}, but no matching providers were registered",
318            config.constraints
319        );
320    }
321    out.push(NeighborhoodLeaf::ConflictRepair(ConflictRepairSelector::new(
322        config.clone(),
323        scalar_variables,
324        repairs,
325    )));
326}
327
328fn push_compound_conflict_repair_selector<S, V, DM, IDM>(
329    config: &solverforge_config::CompoundConflictRepairMoveSelectorConfig,
330    model: &RuntimeModel<S, V, DM, IDM>,
331    out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
332) where
333    S: PlanningSolution + 'static,
334    V: Clone + PartialEq + Send + Sync + Debug + 'static,
335    DM: CrossEntityDistanceMeter<S> + Clone + 'static,
336    IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
337{
338    if config.constraints.is_empty() {
339        panic!("compound_conflict_repair_move_selector requires at least one constraint");
340    }
341    let scalar_variables = model
342        .scalar_variables()
343        .filter(|variable| !model.assignment_group_covers_scalar_variable(variable))
344        .copied()
345        .collect::<Vec<_>>();
346    let repairs = model
347        .conflict_repairs()
348        .iter()
349        .copied()
350        .filter(|repair| {
351            config
352                .constraints
353                .iter()
354                .any(|constraint| constraint == repair.constraint_name())
355        })
356        .collect::<Vec<_>>();
357    if repairs.is_empty() {
358        panic!(
359            "compound_conflict_repair_move_selector configured for {:?}, but no matching providers were registered",
360            config.constraints
361        );
362    }
363    out.push(NeighborhoodLeaf::ConflictRepair(
364        ConflictRepairSelector::new_compound(config.clone(), scalar_variables, repairs),
365    ));
366}
367
368fn push_grouped_scalar_selector<S, V, DM, IDM>(
369    config: &solverforge_config::GroupedScalarMoveSelectorConfig,
370    model: &RuntimeModel<S, V, DM, IDM>,
371    out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
372) where
373    S: PlanningSolution + 'static,
374    V: Clone + PartialEq + Send + Sync + Debug + 'static,
375    DM: CrossEntityDistanceMeter<S> + Clone + 'static,
376    IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
377{
378    let Some(group) = model
379        .scalar_groups()
380        .iter()
381        .find(|group| group.group_name == config.group_name)
382        .cloned()
383    else {
384        panic!(
385            "grouped_scalar_move_selector configured for `{}`, but no matching scalar group was registered",
386            config.group_name
387        );
388    };
389    out.push(NeighborhoodLeaf::GroupedScalar(GroupedScalarSelector::new(
390        group,
391        config.value_candidate_limit,
392        config.max_moves_per_step,
393        config.require_hard_improvement,
394    )));
395}
solverforge_solver/builder/selector/families.rs

solverforge_solver/builder/selector/
families.rs
