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)] enum 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::ListPermuteMoveSelector(_)
123 | MoveSelectorConfig::ListPrecedenceMoveSelector(_)
124 | MoveSelectorConfig::NearbyListSwapMoveSelector(_)
125 | MoveSelectorConfig::SublistChangeMoveSelector(_)
126 | MoveSelectorConfig::SublistSwapMoveSelector(_)
127 | MoveSelectorConfig::ListReverseMoveSelector(_)
128 | MoveSelectorConfig::KOptMoveSelector(_)
129 | MoveSelectorConfig::ListRuinMoveSelector(_) => SelectorFamily::List,
130 MoveSelectorConfig::LimitedNeighborhood(limit) => selector_family(limit.selector.as_ref()),
131 MoveSelectorConfig::UnionMoveSelector(union) => {
132 let mut family = None;
133 for child in &union.selectors {
134 let child_family = selector_family(child);
135 if child_family == SelectorFamily::Unsupported {
136 return SelectorFamily::Unsupported;
137 }
138 family = Some(match family {
139 None => child_family,
140 Some(current) if current == child_family => current,
141 Some(_) => SelectorFamily::Mixed,
142 });
143 if family == Some(SelectorFamily::Mixed) {
144 return SelectorFamily::Mixed;
145 }
146 }
147 family.unwrap_or(SelectorFamily::Mixed)
148 }
149 MoveSelectorConfig::CartesianProductMoveSelector(_) => SelectorFamily::Unsupported,
150 }
151}
152
153fn selector_family_name(config: Option<&MoveSelectorConfig>) -> &'static str {
154 match config.map(selector_family) {
155 None => "default",
156 Some(SelectorFamily::Scalar) => "scalar",
157 Some(SelectorFamily::List) => "list",
158 Some(SelectorFamily::Mixed) => "mixed",
159 Some(SelectorFamily::Unsupported) => "unsupported",
160 }
161}
162
163fn selector_requires_score_during_move(config: &MoveSelectorConfig) -> bool {
164 match config {
165 MoveSelectorConfig::RuinRecreateMoveSelector(_)
166 | MoveSelectorConfig::ListRuinMoveSelector(_) => true,
167 MoveSelectorConfig::LimitedNeighborhood(limit) => {
168 selector_requires_score_during_move(limit.selector.as_ref())
169 }
170 MoveSelectorConfig::UnionMoveSelector(union) => union
171 .selectors
172 .iter()
173 .any(selector_requires_score_during_move),
174 MoveSelectorConfig::CartesianProductMoveSelector(_) => true,
175 _ => false,
176 }
177}
178
179fn assert_cartesian_left_preview_safe(config: &MoveSelectorConfig) {
180 assert!(
181 !selector_requires_score_during_move(config),
182 "cartesian_product left child cannot contain ruin_recreate_move_selector or list_ruin_move_selector because preview directors do not calculate scores",
183 );
184}
185
186fn push_scalar_selector<S, V, DM, IDM>(
187 config: Option<&MoveSelectorConfig>,
188 model: &RuntimeModel<S, V, DM, IDM>,
189 random_seed: Option<u64>,
190 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
191) where
192 S: PlanningSolution + 'static,
193 V: Clone + PartialEq + Send + Sync + Debug + 'static,
194 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
195 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
196{
197 let scalar_variables: Vec<_> = model.scalar_variables().copied().collect();
198 if scalar_variables.is_empty() {
199 return;
200 }
201 if let Some(config) = config {
202 if let Some(variable) = assignment_owned_scalar_target(config, model) {
203 panic!(
204 "scalar move selector targets assignment-owned scalar variable {}.{}; use the owning grouped scalar assignment selector instead",
205 variable.entity_type_name,
206 variable.variable_name
207 );
208 }
209 }
210 let selector = build_scalar_flat_selector(config, &scalar_variables, random_seed);
211 out.extend(
212 selector
213 .into_selectors()
214 .into_iter()
215 .map(NeighborhoodLeaf::Scalar),
216 );
217}
218
219fn matching_dynamic_scalar_variables<S, V, DM, IDM>(
220 config: &MoveSelectorConfig,
221 model: &RuntimeModel<S, V, DM, IDM>,
222) -> Vec<solverforge_core::domain::DynamicScalarVariableSlot<S>> {
223 let target = match config {
224 MoveSelectorConfig::ChangeMoveSelector(config) => Some(&config.target),
225 MoveSelectorConfig::SwapMoveSelector(config) => Some(&config.target),
226 MoveSelectorConfig::NearbyChangeMoveSelector(config) => Some(&config.target),
227 MoveSelectorConfig::NearbySwapMoveSelector(config) => Some(&config.target),
228 MoveSelectorConfig::PillarChangeMoveSelector(config) => Some(&config.target),
229 MoveSelectorConfig::PillarSwapMoveSelector(config) => Some(&config.target),
230 MoveSelectorConfig::RuinRecreateMoveSelector(config) => Some(&config.target),
231 _ => None,
232 };
233 let Some(target) = target else {
234 return Vec::new();
235 };
236 model
237 .dynamic_scalar_variables()
238 .filter(|slot| {
239 slot.matches_target(
240 target.entity_class.as_deref(),
241 target.variable_name.as_deref(),
242 )
243 })
244 .cloned()
245 .collect()
246}
247
248fn push_dynamic_scalar_selector<S, V, DM, IDM>(
249 config: Option<&MoveSelectorConfig>,
250 model: &RuntimeModel<S, V, DM, IDM>,
251 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
252) where
253 S: PlanningSolution + 'static,
254 V: Clone + PartialEq + Send + Sync + Debug + 'static,
255 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
256 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
257{
258 let Some(config) = config else {
259 return;
260 };
261 let matched = matching_dynamic_scalar_variables(config, model);
262 if matched.is_empty() {
263 return;
264 }
265
266 match config {
267 MoveSelectorConfig::ChangeMoveSelector(config) => {
268 for variable in matched {
269 out.push(NeighborhoodLeaf::DynamicScalar(
270 DynamicScalarChangeMoveSelector::new(
271 variable,
272 config.value_candidate_limit,
273 ),
274 ));
275 }
276 }
277 MoveSelectorConfig::SwapMoveSelector(_)
278 | MoveSelectorConfig::NearbyChangeMoveSelector(_)
279 | MoveSelectorConfig::NearbySwapMoveSelector(_)
280 | MoveSelectorConfig::PillarChangeMoveSelector(_)
281 | MoveSelectorConfig::PillarSwapMoveSelector(_)
282 | MoveSelectorConfig::RuinRecreateMoveSelector(_) => {
283 panic!(
284 "dynamic scalar variables currently support change_move_selector; \
285 configured selector matched a dynamic scalar variable but is not bindable"
286 );
287 }
288 _ => {}
289 }
290}
291
292fn assignment_owned_scalar_target<S, V, DM, IDM>(
293 config: &MoveSelectorConfig,
294 model: &RuntimeModel<S, V, DM, IDM>,
295) -> Option<crate::builder::ScalarVariableSlot<S>> {
296 match config {
297 MoveSelectorConfig::ChangeMoveSelector(config) => {
298 target_assignment_owner(&config.target, model)
299 }
300 MoveSelectorConfig::SwapMoveSelector(config) => target_assignment_owner(&config.target, model),
301 MoveSelectorConfig::NearbyChangeMoveSelector(config) => {
302 target_assignment_owner(&config.target, model)
303 }
304 MoveSelectorConfig::NearbySwapMoveSelector(config) => {
305 target_assignment_owner(&config.target, model)
306 }
307 MoveSelectorConfig::PillarChangeMoveSelector(config) => {
308 target_assignment_owner(&config.target, model)
309 }
310 MoveSelectorConfig::PillarSwapMoveSelector(config) => {
311 target_assignment_owner(&config.target, model)
312 }
313 MoveSelectorConfig::RuinRecreateMoveSelector(config) => {
314 target_assignment_owner(&config.target, model)
315 }
316 MoveSelectorConfig::LimitedNeighborhood(limit) => {
317 assignment_owned_scalar_target(limit.selector.as_ref(), model)
318 }
319 MoveSelectorConfig::UnionMoveSelector(union) => union
320 .selectors
321 .iter()
322 .find_map(|selector| assignment_owned_scalar_target(selector, model)),
323 _ => None,
324 }
325}
326
327fn target_assignment_owner<S, V, DM, IDM>(
328 target: &solverforge_config::VariableTargetConfig,
329 model: &RuntimeModel<S, V, DM, IDM>,
330) -> Option<crate::builder::ScalarVariableSlot<S>> {
331 model.scalar_variables().copied().find(|variable| {
332 variable.matches_target(
333 target.entity_class.as_deref(),
334 target.variable_name.as_deref(),
335 ) && model.assignment_group_covers_scalar_variable(variable)
336 })
337}
338
339fn list_selector_target(config: Option<&MoveSelectorConfig>) -> Option<&solverforge_config::VariableTargetConfig> {
340 match config? {
341 MoveSelectorConfig::ListChangeMoveSelector(config) => Some(&config.target),
342 MoveSelectorConfig::NearbyListChangeMoveSelector(config) => Some(&config.target),
343 MoveSelectorConfig::ListSwapMoveSelector(config) => Some(&config.target),
344 MoveSelectorConfig::ListPermuteMoveSelector(config) => Some(&config.target),
345 MoveSelectorConfig::ListPrecedenceMoveSelector(config) => Some(&config.target),
346 MoveSelectorConfig::NearbyListSwapMoveSelector(config) => Some(&config.target),
347 MoveSelectorConfig::SublistChangeMoveSelector(config) => Some(&config.target),
348 MoveSelectorConfig::SublistSwapMoveSelector(config) => Some(&config.target),
349 MoveSelectorConfig::ListReverseMoveSelector(config) => Some(&config.target),
350 MoveSelectorConfig::KOptMoveSelector(config) => Some(&config.target),
351 MoveSelectorConfig::ListRuinMoveSelector(config) => Some(&config.target),
352 _ => None,
353 }
354}
355
356fn push_list_selector<S, V, DM, IDM>(
357 config: Option<&MoveSelectorConfig>,
358 model: &RuntimeModel<S, V, DM, IDM>,
359 random_seed: Option<u64>,
360 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
361) where
362 S: PlanningSolution + 'static,
363 V: Clone + PartialEq + Send + Sync + Debug + 'static,
364 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
365 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
366{
367 let target = list_selector_target(config);
368 for variable in model.list_variables().filter(|variable| {
369 target.is_none_or(|target| {
370 variable.matches_target(
371 target.entity_class.as_deref(),
372 target.variable_name.as_deref(),
373 )
374 })
375 }) {
376 let selector = ListMoveSelectorBuilder::build_flat(config, variable, random_seed);
377 out.extend(
378 selector
379 .into_selectors()
380 .into_iter()
381 .map(NeighborhoodLeaf::List),
382 );
383 }
384}
385
386fn matching_dynamic_list_variables<S, V, DM, IDM>(
387 config: &MoveSelectorConfig,
388 model: &RuntimeModel<S, V, DM, IDM>,
389) -> Vec<solverforge_core::domain::DynamicListVariableSlot<S>> {
390 let target = match config {
391 MoveSelectorConfig::ListChangeMoveSelector(config) => Some(&config.target),
392 MoveSelectorConfig::NearbyListChangeMoveSelector(config) => Some(&config.target),
393 MoveSelectorConfig::ListSwapMoveSelector(config) => Some(&config.target),
394 MoveSelectorConfig::ListPermuteMoveSelector(config) => Some(&config.target),
395 MoveSelectorConfig::ListPrecedenceMoveSelector(config) => Some(&config.target),
396 MoveSelectorConfig::NearbyListSwapMoveSelector(config) => Some(&config.target),
397 MoveSelectorConfig::SublistChangeMoveSelector(config) => Some(&config.target),
398 MoveSelectorConfig::SublistSwapMoveSelector(config) => Some(&config.target),
399 MoveSelectorConfig::ListReverseMoveSelector(config) => Some(&config.target),
400 MoveSelectorConfig::KOptMoveSelector(config) => Some(&config.target),
401 MoveSelectorConfig::ListRuinMoveSelector(config) => Some(&config.target),
402 _ => None,
403 };
404 let Some(target) = target else {
405 return Vec::new();
406 };
407 model
408 .dynamic_list_variables()
409 .filter(|slot| {
410 slot.matches_target(
411 target.entity_class.as_deref(),
412 target.variable_name.as_deref(),
413 )
414 })
415 .cloned()
416 .collect()
417}
418
419fn push_dynamic_list_selector<S, V, DM, IDM>(
420 config: Option<&MoveSelectorConfig>,
421 model: &RuntimeModel<S, V, DM, IDM>,
422 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
423) where
424 S: PlanningSolution + 'static,
425 V: Clone + PartialEq + Send + Sync + Debug + 'static,
426 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
427 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
428{
429 let Some(config) = config else {
430 return;
431 };
432 let matched = matching_dynamic_list_variables(config, model);
433 if matched.is_empty() {
434 return;
435 }
436
437 match config {
438 MoveSelectorConfig::ListChangeMoveSelector(_) => {
439 for variable in matched {
440 out.push(NeighborhoodLeaf::DynamicListChange(
441 DynamicListChangeMoveSelector::new(variable),
442 ));
443 }
444 }
445 MoveSelectorConfig::NearbyListChangeMoveSelector(_)
446 | MoveSelectorConfig::ListSwapMoveSelector(_)
447 | MoveSelectorConfig::ListPermuteMoveSelector(_)
448 | MoveSelectorConfig::ListPrecedenceMoveSelector(_)
449 | MoveSelectorConfig::NearbyListSwapMoveSelector(_)
450 | MoveSelectorConfig::SublistChangeMoveSelector(_)
451 | MoveSelectorConfig::SublistSwapMoveSelector(_)
452 | MoveSelectorConfig::ListReverseMoveSelector(_)
453 | MoveSelectorConfig::KOptMoveSelector(_)
454 | MoveSelectorConfig::ListRuinMoveSelector(_) => {
455 panic!(
456 "dynamic list variables currently support list_change_move_selector; \
457 configured selector matched a dynamic list variable but is not bindable"
458 );
459 }
460 _ => {}
461 }
462}
463
464fn push_conflict_repair_selector<S, V, DM, IDM>(
465 config: &solverforge_config::ConflictRepairMoveSelectorConfig,
466 model: &RuntimeModel<S, V, DM, IDM>,
467 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
468) where
469 S: PlanningSolution + 'static,
470 V: Clone + PartialEq + Send + Sync + Debug + 'static,
471 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
472 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
473{
474 if config.constraints.is_empty() {
475 panic!("conflict_repair_move_selector requires at least one constraint");
476 }
477 let scalar_variables = model
478 .scalar_variables()
479 .filter(|variable| !model.assignment_group_covers_scalar_variable(variable))
480 .copied()
481 .collect::<Vec<_>>();
482 let repairs = model
483 .conflict_repairs()
484 .iter()
485 .copied()
486 .filter(|repair| {
487 config
488 .constraints
489 .iter()
490 .any(|constraint| constraint == repair.constraint_name())
491 })
492 .collect::<Vec<_>>();
493 if repairs.is_empty() {
494 panic!(
495 "conflict_repair_move_selector configured for {:?}, but no matching providers were registered",
496 config.constraints
497 );
498 }
499 out.push(NeighborhoodLeaf::ConflictRepair(ConflictRepairSelector::new(
500 config.clone(),
501 scalar_variables,
502 repairs,
503 )));
504}
505
506fn push_compound_conflict_repair_selector<S, V, DM, IDM>(
507 config: &solverforge_config::CompoundConflictRepairMoveSelectorConfig,
508 model: &RuntimeModel<S, V, DM, IDM>,
509 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
510) where
511 S: PlanningSolution + 'static,
512 V: Clone + PartialEq + Send + Sync + Debug + 'static,
513 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
514 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
515{
516 if config.constraints.is_empty() {
517 panic!("compound_conflict_repair_move_selector requires at least one constraint");
518 }
519 let scalar_variables = model
520 .scalar_variables()
521 .filter(|variable| !model.assignment_group_covers_scalar_variable(variable))
522 .copied()
523 .collect::<Vec<_>>();
524 let repairs = model
525 .conflict_repairs()
526 .iter()
527 .copied()
528 .filter(|repair| {
529 config
530 .constraints
531 .iter()
532 .any(|constraint| constraint == repair.constraint_name())
533 })
534 .collect::<Vec<_>>();
535 if repairs.is_empty() {
536 panic!(
537 "compound_conflict_repair_move_selector configured for {:?}, but no matching providers were registered",
538 config.constraints
539 );
540 }
541 out.push(NeighborhoodLeaf::ConflictRepair(
542 ConflictRepairSelector::new_compound(config.clone(), scalar_variables, repairs),
543 ));
544}
545
546fn push_grouped_scalar_selector<S, V, DM, IDM>(
547 config: &solverforge_config::GroupedScalarMoveSelectorConfig,
548 model: &RuntimeModel<S, V, DM, IDM>,
549 out: &mut Vec<NeighborhoodLeaf<S, V, DM, IDM>>,
550) where
551 S: PlanningSolution + 'static,
552 V: Clone + PartialEq + Send + Sync + Debug + 'static,
553 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
554 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
555{
556 let Some(group) = model
557 .scalar_groups()
558 .iter()
559 .find(|group| group.group_name == config.group_name)
560 .cloned()
561 else {
562 panic!(
563 "grouped_scalar_move_selector configured for `{}`, but no matching scalar group was registered",
564 config.group_name
565 );
566 };
567 out.push(NeighborhoodLeaf::GroupedScalar(GroupedScalarSelector::new(
568 group,
569 config.value_candidate_limit,
570 config.max_moves_per_step,
571 config.require_hard_improvement,
572 )));
573}