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