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 push_dynamic_scalar_selector(config, model, &mut leaves);
24 }
25 Some(MoveSelectorConfig::GroupedScalarMoveSelector(config)) => {
26 push_grouped_scalar_selector(config, model, &mut leaves);
27 }
28 Some(MoveSelectorConfig::ListChangeMoveSelector(_))
29 | Some(MoveSelectorConfig::NearbyListChangeMoveSelector(_))
30 | Some(MoveSelectorConfig::ListSwapMoveSelector(_))
31 | Some(MoveSelectorConfig::ListPermuteMoveSelector(_))
32 | Some(MoveSelectorConfig::ListPrecedenceMoveSelector(_))
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 push_dynamic_list_selector(config, model, &mut leaves);
41 }
42 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
43 for child in &union.selectors {
44 match child {
45 MoveSelectorConfig::GroupedScalarMoveSelector(config) => {
46 push_grouped_scalar_selector(config, model, &mut leaves);
47 continue;
48 }
49 MoveSelectorConfig::ConflictRepairMoveSelector(config) => {
50 push_conflict_repair_selector(config, model, &mut leaves);
51 continue;
52 }
53 MoveSelectorConfig::CompoundConflictRepairMoveSelector(config) => {
54 push_compound_conflict_repair_selector(config, model, &mut leaves);
55 continue;
56 }
57 _ => {}
58 }
59 match selector_family(child) {
60 SelectorFamily::Scalar => {
61 push_scalar_selector(Some(child), model, random_seed, &mut leaves);
62 push_dynamic_scalar_selector(Some(child), model, &mut leaves);
63 }
64 SelectorFamily::List => {
65 push_list_selector(Some(child), model, random_seed, &mut leaves);
66 push_dynamic_list_selector(Some(child), model, &mut leaves);
67 }
68 SelectorFamily::Mixed => {
69 let nested = build_leaf_selector(Some(child), model, random_seed);
70 leaves.extend(nested.into_selectors());
71 }
72 SelectorFamily::Unsupported => {
73 panic!(
74 "cartesian_product move selectors are not supported in the runtime selector graph"
75 );
76 }
77 }
78 }
79 }
80 Some(MoveSelectorConfig::LimitedNeighborhood(_)) => {
81 panic!("limited_neighborhood must be wrapped at the neighborhood level");
82 }
83 Some(MoveSelectorConfig::CartesianProductMoveSelector(_)) => {
84 panic!(
85 "cartesian_product move selectors are not supported in the runtime selector graph"
86 );
87 }
88 Some(MoveSelectorConfig::ConflictRepairMoveSelector(config)) => {
89 push_conflict_repair_selector(config, model, &mut leaves);
90 }
91 Some(MoveSelectorConfig::CompoundConflictRepairMoveSelector(config)) => {
92 push_compound_conflict_repair_selector(config, model, &mut leaves);
93 }
94 }
95 assert!(
96 !leaves.is_empty(),
97 "move selector configuration produced no neighborhoods \
98 (scalar_slots_present={}, list_slots_present={}, requested_selector_family={})",
99 model.has_scalar_variables(),
100 model.has_list_variables(),
101 selector_family_name(config),
102 );
103 let selection_order = match config {
104 Some(MoveSelectorConfig::UnionMoveSelector(union)) => union.selection_order,
105 _ => solverforge_config::UnionSelectionOrder::Sequential,
106 };
107 VecUnionSelector::with_selection_order(leaves, selection_order)
108}
109
110fn build_cartesian_child_selector<S, V, DM, IDM>(
111 config: &MoveSelectorConfig,
112 model: &RuntimeModel<S, V, DM, IDM>,
113 random_seed: Option<u64>,
114) -> CartesianChildSelector<S, V, DM, IDM>
115where
116 S: PlanningSolution + 'static,
117 V: Clone + PartialEq + Send + Sync + Debug + 'static,
118 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
119 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
120{
121 match config {
122 MoveSelectorConfig::LimitedNeighborhood(limit) => CartesianChildSelector::Limited {
123 selector: build_leaf_selector(Some(limit.selector.as_ref()), model, random_seed),
124 selected_count_limit: limit.selected_count_limit,
125 },
126 MoveSelectorConfig::CartesianProductMoveSelector(_) => {
127 panic!("nested cartesian_product move selectors are not supported")
128 }
129 other => CartesianChildSelector::Flat(build_leaf_selector(Some(other), model, random_seed)),
130 }
131}
132
133fn collect_neighborhoods<S, V, DM, IDM>(
134 config: Option<&MoveSelectorConfig>,
135 model: &RuntimeModel<S, V, DM, IDM>,
136 random_seed: Option<u64>,
137 out: &mut Vec<Neighborhood<S, V, DM, IDM>>,
138) where
139 S: PlanningSolution + 'static,
140 V: Clone + PartialEq + Send + Sync + Debug + 'static,
141 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
142 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
143{
144 match config {
145 None => {
146 let Some(default_config) =
147 crate::builder::search::defaults::default_move_selector_config(model)
148 else {
149 return;
150 };
151 collect_neighborhoods(Some(&default_config), model, random_seed, out);
152 }
153 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
154 for child in &union.selectors {
155 collect_neighborhoods(Some(child), model, random_seed, out);
156 }
157 }
158 Some(MoveSelectorConfig::LimitedNeighborhood(limit)) => {
159 let selector = build_leaf_selector(Some(limit.selector.as_ref()), model, random_seed);
160 out.push(Neighborhood::Limited {
161 selector,
162 selected_count_limit: limit.selected_count_limit,
163 });
164 }
165 Some(MoveSelectorConfig::ConflictRepairMoveSelector(config)) => {
166 let mut leaves = Vec::new();
167 push_conflict_repair_selector(config, model, &mut leaves);
168 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
169 }
170 Some(MoveSelectorConfig::CompoundConflictRepairMoveSelector(config)) => {
171 let mut leaves = Vec::new();
172 push_compound_conflict_repair_selector(config, model, &mut leaves);
173 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
174 }
175 Some(MoveSelectorConfig::GroupedScalarMoveSelector(config)) => {
176 let mut leaves = Vec::new();
177 push_grouped_scalar_selector(config, model, &mut leaves);
178 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
179 }
180 Some(MoveSelectorConfig::CartesianProductMoveSelector(cartesian)) => {
181 assert_eq!(
182 cartesian.selectors.len(),
183 2,
184 "cartesian_product move selector requires exactly two child selectors"
185 );
186 assert_cartesian_left_preview_safe(&cartesian.selectors[0]);
187 let left = build_cartesian_child_selector(&cartesian.selectors[0], model, random_seed);
188 let right = build_cartesian_child_selector(&cartesian.selectors[1], model, random_seed);
189 out.push(Neighborhood::Cartesian(
190 CartesianProductSelector::new(left, right)
191 .with_require_hard_improvement(cartesian.require_hard_improvement),
192 ));
193 }
194 Some(other) => out.push(Neighborhood::Flat(build_leaf_selector(
195 Some(other),
196 model,
197 random_seed,
198 ))),
199 }
200}
201
202pub fn build_move_selector<S, V, DM, IDM>(
203 config: Option<&MoveSelectorConfig>,
204 model: &RuntimeModel<S, V, DM, IDM>,
205 random_seed: Option<u64>,
206) -> Selector<S, V, DM, IDM>
207where
208 S: PlanningSolution + 'static,
209 V: Clone + PartialEq + Send + Sync + Debug + 'static,
210 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
211 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
212{
213 model.assert_dynamic_descriptor_indexes_resolved();
214 let mut neighborhoods = Vec::new();
215 let default_config;
216 let effective_config = match config {
217 Some(config) => Some(config),
218 None => {
219 default_config = crate::builder::search::defaults::default_move_selector_config(model);
220 default_config.as_ref()
221 }
222 };
223 collect_neighborhoods(effective_config, model, random_seed, &mut neighborhoods);
224 assert!(
225 !neighborhoods.is_empty(),
226 "move selector configuration produced no neighborhoods \
227 (scalar_slots_present={}, list_slots_present={}, requested_selector_family={})",
228 model.has_scalar_variables(),
229 model.has_list_variables(),
230 selector_family_name(effective_config),
231 );
232 let selection_order = match effective_config {
233 Some(MoveSelectorConfig::UnionMoveSelector(union)) => union.selection_order,
234 _ => solverforge_config::UnionSelectionOrder::Sequential,
235 };
236 VecUnionSelector::with_selection_order(neighborhoods, selection_order)
237}
238
239fn build_acceptor_forager_local_search<S, V, DM, IDM>(
240 config: Option<&LocalSearchConfig>,
241 model: &RuntimeModel<S, V, DM, IDM>,
242 random_seed: Option<u64>,
243) -> LocalSearch<S, V, DM, IDM>
244where
245 S: PlanningSolution + 'static,
246 S::Score: Score + ParseableScore,
247 V: Clone + PartialEq + Send + Sync + Debug + 'static,
248 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
249 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
250{
251 if let Some(config) = config {
252 assert!(
253 config.neighborhoods.is_empty(),
254 "acceptor_forager local_search uses move_selector; neighborhoods are only valid with local_search_type = \"variable_neighborhood_descent\""
255 );
256 }
257
258 let acceptor = config
259 .and_then(|ls| ls.acceptor.as_ref())
260 .map(|cfg| AcceptorBuilder::build_with_seed::<S>(cfg, random_seed))
261 .unwrap_or_else(|| {
262 crate::builder::search::defaults::default_local_search_acceptor(model, random_seed)
263 });
264 let forager = config
265 .and_then(|ls| ls.forager.as_ref())
266 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
267 .unwrap_or_else(|| {
268 let is_tabu = config
269 .and_then(|ls| ls.acceptor.as_ref())
270 .is_some_and(|acceptor| matches!(acceptor, AcceptorConfig::TabuSearch(_)));
271 if is_tabu {
272 AnyForager::BestScore(crate::phase::localsearch::BestScoreForager::new())
273 } else {
274 crate::builder::search::defaults::default_local_search_forager(model)
275 }
276 });
277 let move_selector = build_move_selector(
278 config.and_then(|ls| ls.move_selector.as_ref()),
279 model,
280 random_seed,
281 );
282 let step_limit = config
283 .and_then(|ls| ls.termination.as_ref())
284 .and_then(|termination| termination.step_count_limit);
285
286 LocalSearchPhase::new(move_selector, acceptor, forager, step_limit)
287}
288
289fn build_variable_neighborhood_descent<S, V, DM, IDM>(
290 config: &LocalSearchConfig,
291 model: &RuntimeModel<S, V, DM, IDM>,
292 random_seed: Option<u64>,
293) -> VndPhase<S, NeighborhoodMove<S, V>, Neighborhood<S, V, DM, IDM>>
294where
295 S: PlanningSolution + 'static,
296 S::Score: Score + ParseableScore,
297 V: Clone + PartialEq + Send + Sync + Debug + 'static,
298 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
299 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
300{
301 assert!(
302 config.acceptor.is_none() && config.forager.is_none() && config.move_selector.is_none(),
303 "variable_neighborhood_descent local_search uses neighborhoods; acceptor, forager, and move_selector are only valid with local_search_type = \"acceptor_forager\""
304 );
305 assert!(
306 !config.neighborhoods.is_empty(),
307 "variable_neighborhood_descent local_search requires at least one [[phases.neighborhoods]] block"
308 );
309
310 let neighborhoods = config
311 .neighborhoods
312 .iter()
313 .flat_map(|selector| {
314 let mut neighborhoods = Vec::new();
315 collect_neighborhoods(Some(selector), model, random_seed, &mut neighborhoods);
316 neighborhoods
317 })
318 .collect::<Vec<_>>();
319 assert!(
320 !neighborhoods.is_empty(),
321 "variable_neighborhood_descent local_search neighborhoods produced no move selectors"
322 );
323
324 let step_limit = config
325 .termination
326 .as_ref()
327 .and_then(|termination| termination.step_count_limit);
328
329 VndPhase::new(neighborhoods, step_limit)
330}
331
332pub fn build_local_search<S, V, DM, IDM>(
333 config: Option<&LocalSearchConfig>,
334 model: &RuntimeModel<S, V, DM, IDM>,
335 random_seed: Option<u64>,
336) -> LocalSearchStrategy<S, V, DM, IDM>
337where
338 S: PlanningSolution + 'static,
339 S::Score: Score + ParseableScore,
340 V: Clone + PartialEq + Send + Sync + Debug + 'static,
341 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
342 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
343{
344 model.assert_dynamic_descriptor_indexes_resolved();
345 match config.map(|ls| ls.local_search_type).unwrap_or_default() {
346 LocalSearchType::AcceptorForager => LocalSearchStrategy::acceptor_forager(
347 build_acceptor_forager_local_search(config, model, random_seed),
348 ),
349 LocalSearchType::VariableNeighborhoodDescent => {
350 let config = config.expect(
351 "variable_neighborhood_descent local_search requires an explicit local_search phase",
352 );
353 LocalSearchStrategy::variable_neighborhood_descent(build_variable_neighborhood_descent(
354 config,
355 model,
356 random_seed,
357 ))
358 }
359 }
360}
361
362#[cfg(test)]
363mod tests;