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