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 collect_neighborhoods<S, V, DM, IDM>(
128 config: Option<&MoveSelectorConfig>,
129 model: &RuntimeModel<S, V, DM, IDM>,
130 random_seed: Option<u64>,
131 out: &mut Vec<Neighborhood<S, V, DM, IDM>>,
132) where
133 S: PlanningSolution + 'static,
134 V: Clone + PartialEq + Send + Sync + Debug + 'static,
135 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
136 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
137{
138 match config {
139 None => {
140 let Some(default_config) =
141 crate::builder::search::defaults::default_move_selector_config(model)
142 else {
143 return;
144 };
145 collect_neighborhoods(Some(&default_config), model, random_seed, out);
146 }
147 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
148 for child in &union.selectors {
149 collect_neighborhoods(Some(child), model, random_seed, out);
150 }
151 }
152 Some(MoveSelectorConfig::LimitedNeighborhood(limit)) => {
153 let selector = build_leaf_selector(Some(limit.selector.as_ref()), model, random_seed);
154 out.push(Neighborhood::Limited {
155 selector,
156 selected_count_limit: limit.selected_count_limit,
157 });
158 }
159 Some(MoveSelectorConfig::ConflictRepairMoveSelector(config)) => {
160 let mut leaves = Vec::new();
161 push_conflict_repair_selector(config, model, &mut leaves);
162 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
163 }
164 Some(MoveSelectorConfig::CompoundConflictRepairMoveSelector(config)) => {
165 let mut leaves = Vec::new();
166 push_compound_conflict_repair_selector(config, model, &mut leaves);
167 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
168 }
169 Some(MoveSelectorConfig::GroupedScalarMoveSelector(config)) => {
170 let mut leaves = Vec::new();
171 push_grouped_scalar_selector(config, model, &mut leaves);
172 out.push(Neighborhood::Flat(VecUnionSelector::new(leaves)));
173 }
174 Some(MoveSelectorConfig::CartesianProductMoveSelector(cartesian)) => {
175 assert_eq!(
176 cartesian.selectors.len(),
177 2,
178 "cartesian_product move selector requires exactly two child selectors"
179 );
180 assert_cartesian_left_preview_safe(&cartesian.selectors[0]);
181 let left = build_cartesian_child_selector(&cartesian.selectors[0], model, random_seed);
182 let right = build_cartesian_child_selector(&cartesian.selectors[1], model, random_seed);
183 out.push(Neighborhood::Cartesian(
184 CartesianProductSelector::new(left, right)
185 .with_require_hard_improvement(cartesian.require_hard_improvement),
186 ));
187 }
188 Some(other) => out.push(Neighborhood::Flat(build_leaf_selector(
189 Some(other),
190 model,
191 random_seed,
192 ))),
193 }
194}
195
196pub fn build_move_selector<S, V, DM, IDM>(
197 config: Option<&MoveSelectorConfig>,
198 model: &RuntimeModel<S, V, DM, IDM>,
199 random_seed: Option<u64>,
200) -> Selector<S, V, DM, IDM>
201where
202 S: PlanningSolution + 'static,
203 V: Clone + PartialEq + Send + Sync + Debug + 'static,
204 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
205 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
206{
207 let mut neighborhoods = Vec::new();
208 let default_config;
209 let effective_config = match config {
210 Some(config) => Some(config),
211 None => {
212 default_config = crate::builder::search::defaults::default_move_selector_config(model);
213 default_config.as_ref()
214 }
215 };
216 collect_neighborhoods(effective_config, model, random_seed, &mut neighborhoods);
217 assert!(
218 !neighborhoods.is_empty(),
219 "move selector configuration produced no neighborhoods \
220 (scalar_slots_present={}, list_slots_present={}, requested_selector_family={})",
221 model.scalar_variables().next().is_some(),
222 model.has_list_variables(),
223 selector_family_name(effective_config),
224 );
225 let selection_order = match effective_config {
226 Some(MoveSelectorConfig::UnionMoveSelector(union)) => union.selection_order,
227 _ => solverforge_config::UnionSelectionOrder::Sequential,
228 };
229 VecUnionSelector::with_selection_order(neighborhoods, selection_order)
230}
231
232fn build_acceptor_forager_local_search<S, V, DM, IDM>(
233 config: Option<&LocalSearchConfig>,
234 model: &RuntimeModel<S, V, DM, IDM>,
235 random_seed: Option<u64>,
236) -> LocalSearch<S, V, DM, IDM>
237where
238 S: PlanningSolution + 'static,
239 S::Score: Score + ParseableScore,
240 V: Clone + PartialEq + Send + Sync + Debug + 'static,
241 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
242 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
243{
244 if let Some(config) = config {
245 assert!(
246 config.neighborhoods.is_empty(),
247 "acceptor_forager local_search uses move_selector; neighborhoods are only valid with local_search_type = \"variable_neighborhood_descent\""
248 );
249 }
250
251 let acceptor = config
252 .and_then(|ls| ls.acceptor.as_ref())
253 .map(|cfg| AcceptorBuilder::build_with_seed::<S>(cfg, random_seed))
254 .unwrap_or_else(|| {
255 crate::builder::search::defaults::default_local_search_acceptor(model, random_seed)
256 });
257 let forager = config
258 .and_then(|ls| ls.forager.as_ref())
259 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
260 .unwrap_or_else(|| {
261 let is_tabu = config
262 .and_then(|ls| ls.acceptor.as_ref())
263 .is_some_and(|acceptor| matches!(acceptor, AcceptorConfig::TabuSearch(_)));
264 if is_tabu {
265 AnyForager::BestScore(crate::phase::localsearch::BestScoreForager::new())
266 } else {
267 crate::builder::search::defaults::default_local_search_forager(model)
268 }
269 });
270 let move_selector = build_move_selector(
271 config.and_then(|ls| ls.move_selector.as_ref()),
272 model,
273 random_seed,
274 );
275 let step_limit = config
276 .and_then(|ls| ls.termination.as_ref())
277 .and_then(|termination| termination.step_count_limit);
278
279 LocalSearchPhase::new(move_selector, acceptor, forager, step_limit)
280}
281
282fn build_variable_neighborhood_descent<S, V, DM, IDM>(
283 config: &LocalSearchConfig,
284 model: &RuntimeModel<S, V, DM, IDM>,
285 random_seed: Option<u64>,
286) -> VndPhase<S, NeighborhoodMove<S, V>, Neighborhood<S, V, DM, IDM>>
287where
288 S: PlanningSolution + 'static,
289 S::Score: Score + ParseableScore,
290 V: Clone + PartialEq + Send + Sync + Debug + 'static,
291 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
292 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
293{
294 assert!(
295 config.acceptor.is_none() && config.forager.is_none() && config.move_selector.is_none(),
296 "variable_neighborhood_descent local_search uses neighborhoods; acceptor, forager, and move_selector are only valid with local_search_type = \"acceptor_forager\""
297 );
298 assert!(
299 !config.neighborhoods.is_empty(),
300 "variable_neighborhood_descent local_search requires at least one [[phases.neighborhoods]] block"
301 );
302
303 let neighborhoods = config
304 .neighborhoods
305 .iter()
306 .flat_map(|selector| {
307 let mut neighborhoods = Vec::new();
308 collect_neighborhoods(Some(selector), model, random_seed, &mut neighborhoods);
309 neighborhoods
310 })
311 .collect::<Vec<_>>();
312 assert!(
313 !neighborhoods.is_empty(),
314 "variable_neighborhood_descent local_search neighborhoods produced no move selectors"
315 );
316
317 let step_limit = config
318 .termination
319 .as_ref()
320 .and_then(|termination| termination.step_count_limit);
321
322 VndPhase::new(neighborhoods, step_limit)
323}
324
325pub fn build_local_search<S, V, DM, IDM>(
326 config: Option<&LocalSearchConfig>,
327 model: &RuntimeModel<S, V, DM, IDM>,
328 random_seed: Option<u64>,
329) -> LocalSearchStrategy<S, V, DM, IDM>
330where
331 S: PlanningSolution + 'static,
332 S::Score: Score + ParseableScore,
333 V: Clone + PartialEq + Send + Sync + Debug + 'static,
334 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
335 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
336{
337 match config.map(|ls| ls.local_search_type).unwrap_or_default() {
338 LocalSearchType::AcceptorForager => LocalSearchStrategy::acceptor_forager(
339 build_acceptor_forager_local_search(config, model, random_seed),
340 ),
341 LocalSearchType::VariableNeighborhoodDescent => {
342 let config = config.expect(
343 "variable_neighborhood_descent local_search requires an explicit local_search phase",
344 );
345 LocalSearchStrategy::variable_neighborhood_descent(build_variable_neighborhood_descent(
346 config,
347 model,
348 random_seed,
349 ))
350 }
351 }
352}
353
354#[cfg(test)]
355mod tests;