1fn build_leaf_selector<S, V, DM, IDM>(
2 config: Option<&MoveSelectorConfig>,
3 model: &RuntimeModel<S, V, DM, IDM>,
4 random_seed: Option<u64>,
5) -> LeafSelector<S, V, DM, IDM>
6where
7 S: PlanningSolution + 'static,
8 V: Clone + PartialEq + Send + Sync + Debug + 'static,
9 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
10 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
11{
12 let mut leaves = Vec::new();
13 match config {
14 None => unreachable!("default neighborhoods must be resolved before leaf selection"),
15 Some(MoveSelectorConfig::ChangeMoveSelector(_))
16 | Some(MoveSelectorConfig::SwapMoveSelector(_))
17 | Some(MoveSelectorConfig::NearbyChangeMoveSelector(_))
18 | Some(MoveSelectorConfig::NearbySwapMoveSelector(_))
19 | Some(MoveSelectorConfig::PillarChangeMoveSelector(_))
20 | Some(MoveSelectorConfig::PillarSwapMoveSelector(_))
21 | Some(MoveSelectorConfig::RuinRecreateMoveSelector(_)) => {
22 push_scalar_selector(config, model, random_seed, &mut leaves);
23 }
24 Some(MoveSelectorConfig::GroupedScalarMoveSelector(config)) => {
25 push_grouped_scalar_selector(config, model, &mut leaves);
26 }
27 Some(MoveSelectorConfig::CoverageRepairMoveSelector(config)) => {
28 push_coverage_repair_selector(config, model, &mut leaves);
29 }
30 Some(MoveSelectorConfig::ListChangeMoveSelector(_))
31 | Some(MoveSelectorConfig::NearbyListChangeMoveSelector(_))
32 | Some(MoveSelectorConfig::ListSwapMoveSelector(_))
33 | Some(MoveSelectorConfig::NearbyListSwapMoveSelector(_))
34 | Some(MoveSelectorConfig::SublistChangeMoveSelector(_))
35 | Some(MoveSelectorConfig::SublistSwapMoveSelector(_))
36 | Some(MoveSelectorConfig::ListReverseMoveSelector(_))
37 | Some(MoveSelectorConfig::KOptMoveSelector(_))
38 | Some(MoveSelectorConfig::ListRuinMoveSelector(_)) => {
39 push_list_selector(config, model, random_seed, &mut leaves);
40 }
41 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
42 for child in &union.selectors {
43 match child {
44 MoveSelectorConfig::GroupedScalarMoveSelector(config) => {
45 push_grouped_scalar_selector(config, model, &mut leaves);
46 continue;
47 }
48 MoveSelectorConfig::CoverageRepairMoveSelector(config) => {
49 push_coverage_repair_selector(config, model, &mut leaves);
50 continue;
51 }
52 MoveSelectorConfig::ConflictRepairMoveSelector(config) => {
53 push_conflict_repair_selector(config, model, &mut leaves);
54 continue;
55 }
56 MoveSelectorConfig::CompoundConflictRepairMoveSelector(config) => {
57 push_compound_conflict_repair_selector(config, model, &mut leaves);
58 continue;
59 }
60 _ => {}
61 }
62 match selector_family(child) {
63 SelectorFamily::Scalar => {
64 push_scalar_selector(Some(child), model, random_seed, &mut leaves);
65 }
66 SelectorFamily::List => {
67 push_list_selector(Some(child), model, random_seed, &mut leaves);
68 }
69 SelectorFamily::Mixed => {
70 let nested = build_leaf_selector(Some(child), model, random_seed);
71 leaves.extend(nested.into_selectors());
72 }
73 SelectorFamily::Unsupported => {
74 panic!(
75 "cartesian_product move selectors are not supported in the runtime selector graph"
76 );
77 }
78 }
79 }
80 }
81 Some(MoveSelectorConfig::LimitedNeighborhood(_)) => {
82 panic!("limited_neighborhood must be wrapped at the neighborhood level");
83 }
84 Some(MoveSelectorConfig::CartesianProductMoveSelector(_)) => {
85 panic!(
86 "cartesian_product move selectors are not supported in the runtime selector graph"
87 );
88 }
89 Some(MoveSelectorConfig::ConflictRepairMoveSelector(config)) => {
90 push_conflict_repair_selector(config, model, &mut leaves);
91 }
92 Some(MoveSelectorConfig::CompoundConflictRepairMoveSelector(config)) => {
93 push_compound_conflict_repair_selector(config, model, &mut leaves);
94 }
95 }
96 assert!(
97 !leaves.is_empty(),
98 "move selector configuration produced no neighborhoods \
99 (scalar_slots_present={}, list_slots_present={}, requested_selector_family={})",
100 model.scalar_variables().next().is_some(),
101 model.has_list_variables(),
102 selector_family_name(config),
103 );
104 let selection_order = match config {
105 Some(MoveSelectorConfig::UnionMoveSelector(union)) => union.selection_order,
106 _ => solverforge_config::UnionSelectionOrder::Sequential,
107 };
108 VecUnionSelector::with_selection_order(leaves, selection_order)
109}
110
111fn build_cartesian_child_selector<S, V, DM, IDM>(
112 config: &MoveSelectorConfig,
113 model: &RuntimeModel<S, V, DM, IDM>,
114 random_seed: Option<u64>,
115) -> CartesianChildSelector<S, V, DM, IDM>
116where
117 S: PlanningSolution + 'static,
118 V: Clone + PartialEq + Send + Sync + Debug + 'static,
119 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
120 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
121{
122 match config {
123 MoveSelectorConfig::LimitedNeighborhood(limit) => CartesianChildSelector::Limited {
124 selector: build_leaf_selector(Some(limit.selector.as_ref()), model, random_seed),
125 selected_count_limit: limit.selected_count_limit,
126 },
127 MoveSelectorConfig::CartesianProductMoveSelector(_) => {
128 panic!("nested cartesian_product move selectors are not supported")
129 }
130 other => CartesianChildSelector::Flat(build_leaf_selector(Some(other), model, random_seed)),
131 }
132}
133
134fn wrap_neighborhood_composite<S, V>(
135 mov: SequentialCompositeMove<S, NeighborhoodMove<S, V>>,
136) -> NeighborhoodMove<S, V>
137where
138 S: PlanningSolution,
139 V: Clone + PartialEq + Send + Sync + Debug + 'static,
140{
141 NeighborhoodMove::Composite(mov)
142}
143
144fn default_scalar_change_selector() -> MoveSelectorConfig {
145 MoveSelectorConfig::ChangeMoveSelector(ChangeMoveConfig {
146 value_candidate_limit: None,
147 target: VariableTargetConfig::default(),
148 })
149}
150
151fn default_scalar_swap_selector() -> MoveSelectorConfig {
152 MoveSelectorConfig::SwapMoveSelector(solverforge_config::SwapMoveConfig {
153 target: VariableTargetConfig::default(),
154 })
155}
156
157fn default_nearby_list_change_selector() -> MoveSelectorConfig {
158 MoveSelectorConfig::NearbyListChangeMoveSelector(NearbyListChangeMoveConfig {
159 max_nearby: 20,
160 target: VariableTargetConfig::default(),
161 })
162}
163
164fn default_nearby_list_swap_selector() -> MoveSelectorConfig {
165 MoveSelectorConfig::NearbyListSwapMoveSelector(NearbyListSwapMoveConfig {
166 max_nearby: 20,
167 target: VariableTargetConfig::default(),
168 })
169}
170
171fn default_list_reverse_selector() -> MoveSelectorConfig {
172 MoveSelectorConfig::ListReverseMoveSelector(ListReverseMoveConfig {
173 target: VariableTargetConfig::default(),
174 })
175}
176
177fn collect_default_neighborhoods<S, V, DM, IDM>(
178 model: &RuntimeModel<S, V, DM, IDM>,
179 random_seed: Option<u64>,
180 out: &mut Vec<Neighborhood<S, V, DM, IDM>>,
181) where
182 S: PlanningSolution + 'static,
183 V: Clone + PartialEq + Send + Sync + Debug + 'static,
184 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
185 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
186{
187 if model.has_list_variables() {
188 let list_change = default_nearby_list_change_selector();
189 out.push(Neighborhood::Flat(build_leaf_selector(
190 Some(&list_change),
191 model,
192 random_seed,
193 )));
194
195 let list_swap = default_nearby_list_swap_selector();
196 out.push(Neighborhood::Flat(build_leaf_selector(
197 Some(&list_swap),
198 model,
199 random_seed,
200 )));
201
202 let list_reverse = default_list_reverse_selector();
203 out.push(Neighborhood::Flat(build_leaf_selector(
204 Some(&list_reverse),
205 model,
206 random_seed,
207 )));
208 }
209
210 if model.scalar_variables().next().is_some() {
211 let scalar_change = default_scalar_change_selector();
212 out.push(Neighborhood::Flat(build_leaf_selector(
213 Some(&scalar_change),
214 model,
215 random_seed,
216 )));
217
218 let scalar_swap = default_scalar_swap_selector();
219 out.push(Neighborhood::Flat(build_leaf_selector(
220 Some(&scalar_swap),
221 model,
222 random_seed,
223 )));
224 }
225}
226
227fn collect_neighborhoods<S, V, DM, IDM>(
228 config: Option<&MoveSelectorConfig>,
229 model: &RuntimeModel<S, V, DM, IDM>,
230 random_seed: Option<u64>,
231 out: &mut Vec<Neighborhood<S, V, DM, IDM>>,
232) where
233 S: PlanningSolution + 'static,
234 V: Clone + PartialEq + Send + Sync + Debug + 'static,
235 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
236 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
237{
238 match config {
239 None => collect_default_neighborhoods(model, random_seed, out),
240 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
241 for child in &union.selectors {
242 collect_neighborhoods(Some(child), model, random_seed, out);
243 }
244 }
245 Some(MoveSelectorConfig::LimitedNeighborhood(limit)) => {
246 let selector = build_leaf_selector(Some(limit.selector.as_ref()), model, random_seed);
247 out.push(Neighborhood::Limited {
248 selector,
249 selected_count_limit: limit.selected_count_limit,
250 });
251 }
252 Some(MoveSelectorConfig::ConflictRepairMoveSelector(config)) => {
253 let mut leaves = Vec::new();
254 push_conflict_repair_selector(config, model, &mut leaves);
255 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
256 }
257 Some(MoveSelectorConfig::CompoundConflictRepairMoveSelector(config)) => {
258 let mut leaves = Vec::new();
259 push_compound_conflict_repair_selector(config, model, &mut leaves);
260 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
261 }
262 Some(MoveSelectorConfig::GroupedScalarMoveSelector(config)) => {
263 let mut leaves = Vec::new();
264 push_grouped_scalar_selector(config, model, &mut leaves);
265 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
266 }
267 Some(MoveSelectorConfig::CoverageRepairMoveSelector(config)) => {
268 let mut leaves = Vec::new();
269 push_coverage_repair_selector(config, model, &mut leaves);
270 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
271 }
272 Some(MoveSelectorConfig::CartesianProductMoveSelector(cartesian)) => {
273 assert_eq!(
274 cartesian.selectors.len(),
275 2,
276 "cartesian_product move selector requires exactly two child selectors"
277 );
278 assert_cartesian_left_preview_safe(&cartesian.selectors[0]);
279 let left = build_cartesian_child_selector(&cartesian.selectors[0], model, random_seed);
280 let right = build_cartesian_child_selector(&cartesian.selectors[1], model, random_seed);
281 out.push(Neighborhood::Cartesian(
282 CartesianProductSelector::new(left, right, wrap_neighborhood_composite::<S, V>)
283 .with_require_hard_improvement(cartesian.require_hard_improvement),
284 ));
285 }
286 Some(other) => out.push(Neighborhood::Flat(build_leaf_selector(
287 Some(other),
288 model,
289 random_seed,
290 ))),
291 }
292}
293
294pub fn build_move_selector<S, V, DM, IDM>(
295 config: Option<&MoveSelectorConfig>,
296 model: &RuntimeModel<S, V, DM, IDM>,
297 random_seed: Option<u64>,
298) -> Selector<S, V, DM, IDM>
299where
300 S: PlanningSolution + 'static,
301 V: Clone + PartialEq + Send + Sync + Debug + 'static,
302 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
303 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
304{
305 let mut neighborhoods = Vec::new();
306 collect_neighborhoods(config, model, random_seed, &mut neighborhoods);
307 assert!(
308 !neighborhoods.is_empty(),
309 "move selector configuration produced no neighborhoods \
310 (scalar_slots_present={}, list_slots_present={}, requested_selector_family={})",
311 model.scalar_variables().next().is_some(),
312 model.has_list_variables(),
313 selector_family_name(config),
314 );
315 let selection_order = match config {
316 Some(MoveSelectorConfig::UnionMoveSelector(union)) => union.selection_order,
317 _ => solverforge_config::UnionSelectionOrder::Sequential,
318 };
319 VecUnionSelector::with_selection_order(neighborhoods, selection_order)
320}
321
322pub fn build_local_search<S, V, DM, IDM>(
323 config: Option<&LocalSearchConfig>,
324 model: &RuntimeModel<S, V, DM, IDM>,
325 random_seed: Option<u64>,
326) -> LocalSearch<S, V, DM, IDM>
327where
328 S: PlanningSolution + 'static,
329 S::Score: Score + ParseableScore,
330 V: Clone + PartialEq + Send + Sync + Debug + 'static,
331 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
332 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
333{
334 let acceptor = config
335 .and_then(|ls| ls.acceptor.as_ref())
336 .map(|cfg| AcceptorBuilder::build_with_seed::<S>(cfg, random_seed))
337 .unwrap_or_else(|| {
338 if model.has_list_variables() {
339 AnyAcceptor::LateAcceptance(
340 crate::phase::localsearch::LateAcceptanceAcceptor::<S>::new(400),
341 )
342 } else {
343 match random_seed {
344 Some(seed) => AnyAcceptor::SimulatedAnnealing(
345 SimulatedAnnealingAcceptor::auto_calibrate_with_seed(0.999985, seed),
346 ),
347 None => AnyAcceptor::SimulatedAnnealing(SimulatedAnnealingAcceptor::default()),
348 }
349 }
350 });
351 let forager = config
352 .and_then(|ls| ls.forager.as_ref())
353 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
354 .unwrap_or_else(|| {
355 let is_tabu = config
356 .and_then(|ls| ls.acceptor.as_ref())
357 .is_some_and(|acceptor| matches!(acceptor, AcceptorConfig::TabuSearch(_)));
358 if is_tabu {
359 AnyForager::BestScore(crate::phase::localsearch::BestScoreForager::new())
360 } else {
361 let accepted = if model.has_list_variables() { 4 } else { 1 };
362 AnyForager::AcceptedCount(AcceptedCountForager::new(accepted))
363 }
364 });
365 let move_selector = build_move_selector(
366 config.and_then(|ls| ls.move_selector.as_ref()),
367 model,
368 random_seed,
369 );
370 let step_limit = config
371 .and_then(|ls| ls.termination.as_ref())
372 .and_then(|termination| termination.step_count_limit);
373
374 LocalSearchPhase::new(move_selector, acceptor, forager, step_limit)
375}
376
377pub fn build_vnd<S, V, DM, IDM>(
378 config: &VndConfig,
379 model: &RuntimeModel<S, V, DM, IDM>,
380 random_seed: Option<u64>,
381) -> Vnd<S, V, DM, IDM>
382where
383 S: PlanningSolution + 'static,
384 S::Score: Score + ParseableScore,
385 V: Clone + PartialEq + Send + Sync + Debug + 'static,
386 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
387 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
388{
389 let neighborhoods = if config.neighborhoods.is_empty() {
390 let mut neighborhoods = Vec::new();
391 collect_neighborhoods(None, model, random_seed, &mut neighborhoods);
392 neighborhoods
393 } else {
394 config
395 .neighborhoods
396 .iter()
397 .flat_map(|selector| {
398 let mut neighborhoods = Vec::new();
399 collect_neighborhoods(Some(selector), model, random_seed, &mut neighborhoods);
400 neighborhoods
401 })
402 .collect()
403 };
404
405 DynamicVndPhase::new(neighborhoods)
406}
407
408#[cfg(test)]
409mod tests;