1use std::fmt::{self, Debug};
2
3use solverforge_config::{LocalSearchConfig, MoveSelectorConfig, VndConfig};
4use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
5use solverforge_core::score::{ParseableScore, Score};
6
7use crate::builder::{
8 AcceptorBuilder, AnyAcceptor, AnyForager, ForagerBuilder, ListContext, ListLeafSelector,
9 ListMoveSelectorBuilder,
10};
11use crate::descriptor_standard::{
12 build_descriptor_move_selector, descriptor_has_bindings, DescriptorEitherMove,
13 DescriptorLeafSelector,
14};
15use crate::heuristic::r#move::{ListMoveImpl, Move, MoveArena};
16use crate::heuristic::selector::decorator::{SelectedCountLimitMoveSelector, VecUnionSelector};
17use crate::heuristic::selector::move_selector::MoveSelector;
18use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
19use crate::phase::dynamic_vnd::DynamicVndPhase;
20use crate::phase::localsearch::{
21 AcceptedCountForager, LocalSearchPhase, SimulatedAnnealingAcceptor,
22};
23
24type StandardSelector<S> = VecUnionSelector<S, DescriptorEitherMove<S>, DescriptorLeafSelector<S>>;
25type LimitedStandardSelector<S> =
26 SelectedCountLimitMoveSelector<S, DescriptorEitherMove<S>, StandardSelector<S>>;
27type ListSelector<S, V, DM, IDM> =
28 VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>;
29type LimitedListSelector<S, V, DM, IDM> =
30 SelectedCountLimitMoveSelector<S, ListMoveImpl<S, V>, ListSelector<S, V, DM, IDM>>;
31
32pub enum UnifiedMove<S, V> {
33 Standard(DescriptorEitherMove<S>),
34 List(ListMoveImpl<S, V>),
35}
36
37impl<S, V> Debug for UnifiedMove<S, V>
38where
39 S: PlanningSolution + 'static,
40 V: Clone + PartialEq + Send + Sync + Debug + 'static,
41{
42 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
43 match self {
44 Self::Standard(m) => write!(f, "UnifiedMove::Standard({m:?})"),
45 Self::List(m) => write!(f, "UnifiedMove::List({m:?})"),
46 }
47 }
48}
49
50impl<S, V> Move<S> for UnifiedMove<S, V>
51where
52 S: PlanningSolution + 'static,
53 V: Clone + PartialEq + Send + Sync + Debug + 'static,
54{
55 fn is_doable<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> bool {
56 match self {
57 Self::Standard(m) => m.is_doable(score_director),
58 Self::List(m) => m.is_doable(score_director),
59 }
60 }
61
62 fn do_move<D: solverforge_scoring::Director<S>>(&self, score_director: &mut D) {
63 match self {
64 Self::Standard(m) => m.do_move(score_director),
65 Self::List(m) => m.do_move(score_director),
66 }
67 }
68
69 fn descriptor_index(&self) -> usize {
70 match self {
71 Self::Standard(m) => m.descriptor_index(),
72 Self::List(m) => m.descriptor_index(),
73 }
74 }
75
76 fn entity_indices(&self) -> &[usize] {
77 match self {
78 Self::Standard(m) => m.entity_indices(),
79 Self::List(m) => m.entity_indices(),
80 }
81 }
82
83 fn variable_name(&self) -> &str {
84 match self {
85 Self::Standard(m) => m.variable_name(),
86 Self::List(m) => m.variable_name(),
87 }
88 }
89}
90
91pub enum UnifiedNeighborhood<S, V, DM, IDM>
92where
93 S: PlanningSolution + 'static,
94 V: Clone + PartialEq + Send + Sync + Debug + 'static,
95 DM: CrossEntityDistanceMeter<S> + Clone,
96 IDM: CrossEntityDistanceMeter<S> + Clone,
97{
98 Standard(StandardSelector<S>),
99 LimitedStandard(LimitedStandardSelector<S>),
100 List(ListSelector<S, V, DM, IDM>),
101 LimitedList(LimitedListSelector<S, V, DM, IDM>),
102}
103
104impl<S, V, DM, IDM> Debug for UnifiedNeighborhood<S, V, DM, IDM>
105where
106 S: PlanningSolution + 'static,
107 V: Clone + PartialEq + Send + Sync + Debug + 'static,
108 DM: CrossEntityDistanceMeter<S> + Clone + Debug,
109 IDM: CrossEntityDistanceMeter<S> + Clone + Debug,
110{
111 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112 match self {
113 Self::Standard(s) => write!(f, "UnifiedNeighborhood::Standard({s:?})"),
114 Self::LimitedStandard(s) => write!(f, "UnifiedNeighborhood::LimitedStandard({s:?})"),
115 Self::List(s) => write!(f, "UnifiedNeighborhood::List({s:?})"),
116 Self::LimitedList(s) => write!(f, "UnifiedNeighborhood::LimitedList({s:?})"),
117 }
118 }
119}
120
121impl<S, V, DM, IDM> MoveSelector<S, UnifiedMove<S, V>> for UnifiedNeighborhood<S, V, DM, IDM>
122where
123 S: PlanningSolution + 'static,
124 V: Clone + PartialEq + Send + Sync + Debug + 'static,
125 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
126 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
127{
128 fn iter_moves<'a, D: solverforge_scoring::Director<S>>(
129 &'a self,
130 score_director: &'a D,
131 ) -> impl Iterator<Item = UnifiedMove<S, V>> + 'a {
132 enum UnifiedNeighborhoodIter<A, B, C, DIter> {
133 Standard(A),
134 LimitedStandard(B),
135 List(C),
136 LimitedList(DIter),
137 }
138
139 impl<T, A, B, C, DIter> Iterator for UnifiedNeighborhoodIter<A, B, C, DIter>
140 where
141 A: Iterator<Item = T>,
142 B: Iterator<Item = T>,
143 C: Iterator<Item = T>,
144 DIter: Iterator<Item = T>,
145 {
146 type Item = T;
147
148 fn next(&mut self) -> Option<Self::Item> {
149 match self {
150 Self::Standard(iter) => iter.next(),
151 Self::LimitedStandard(iter) => iter.next(),
152 Self::List(iter) => iter.next(),
153 Self::LimitedList(iter) => iter.next(),
154 }
155 }
156 }
157
158 match self {
159 Self::Standard(selector) => UnifiedNeighborhoodIter::Standard(
160 selector
161 .iter_moves(score_director)
162 .map(UnifiedMove::Standard),
163 ),
164 Self::LimitedStandard(selector) => UnifiedNeighborhoodIter::LimitedStandard(
165 selector
166 .iter_moves(score_director)
167 .map(UnifiedMove::Standard),
168 ),
169 Self::List(selector) => UnifiedNeighborhoodIter::List(
170 selector.iter_moves(score_director).map(UnifiedMove::List),
171 ),
172 Self::LimitedList(selector) => UnifiedNeighborhoodIter::LimitedList(
173 selector.iter_moves(score_director).map(UnifiedMove::List),
174 ),
175 }
176 }
177
178 fn size<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> usize {
179 match self {
180 Self::Standard(selector) => selector.size(score_director),
181 Self::LimitedStandard(selector) => selector.size(score_director),
182 Self::List(selector) => selector.size(score_director),
183 Self::LimitedList(selector) => selector.size(score_director),
184 }
185 }
186
187 fn append_moves<D: solverforge_scoring::Director<S>>(
188 &self,
189 score_director: &D,
190 arena: &mut MoveArena<UnifiedMove<S, V>>,
191 ) {
192 match self {
193 Self::Standard(selector) => {
194 for mov in selector.iter_moves(score_director) {
195 arena.push(UnifiedMove::Standard(mov));
196 }
197 }
198 Self::LimitedStandard(selector) => {
199 for mov in selector.iter_moves(score_director) {
200 arena.push(UnifiedMove::Standard(mov));
201 }
202 }
203 Self::List(selector) => {
204 for mov in selector.iter_moves(score_director) {
205 arena.push(UnifiedMove::List(mov));
206 }
207 }
208 Self::LimitedList(selector) => {
209 for mov in selector.iter_moves(score_director) {
210 arena.push(UnifiedMove::List(mov));
211 }
212 }
213 }
214 }
215}
216
217#[derive(Clone, Copy, Debug, PartialEq, Eq)]
218enum SelectorFamily {
219 Standard,
220 List,
221 Mixed,
222 Unsupported,
223}
224
225fn selector_family(config: &MoveSelectorConfig) -> SelectorFamily {
226 match config {
227 MoveSelectorConfig::ChangeMoveSelector(_) | MoveSelectorConfig::SwapMoveSelector(_) => {
228 SelectorFamily::Standard
229 }
230 MoveSelectorConfig::ListChangeMoveSelector(_)
231 | MoveSelectorConfig::NearbyListChangeMoveSelector(_)
232 | MoveSelectorConfig::ListSwapMoveSelector(_)
233 | MoveSelectorConfig::NearbyListSwapMoveSelector(_)
234 | MoveSelectorConfig::SubListChangeMoveSelector(_)
235 | MoveSelectorConfig::SubListSwapMoveSelector(_)
236 | MoveSelectorConfig::ListReverseMoveSelector(_)
237 | MoveSelectorConfig::KOptMoveSelector(_)
238 | MoveSelectorConfig::ListRuinMoveSelector(_) => SelectorFamily::List,
239 MoveSelectorConfig::SelectedCountLimitMoveSelector(limit) => {
240 selector_family(limit.selector.as_ref())
241 }
242 MoveSelectorConfig::UnionMoveSelector(union) => {
243 let mut family = None;
244 for child in &union.selectors {
245 let child_family = selector_family(child);
246 if child_family == SelectorFamily::Unsupported {
247 return SelectorFamily::Unsupported;
248 }
249 family = Some(match family {
250 None => child_family,
251 Some(current) if current == child_family => current,
252 Some(_) => SelectorFamily::Mixed,
253 });
254 if family == Some(SelectorFamily::Mixed) {
255 return SelectorFamily::Mixed;
256 }
257 }
258 family.unwrap_or(SelectorFamily::Mixed)
259 }
260 MoveSelectorConfig::CartesianProductMoveSelector(_) => SelectorFamily::Unsupported,
261 }
262}
263
264pub type UnifiedLocalSearch<S, V, DM, IDM> = LocalSearchPhase<
265 S,
266 UnifiedMove<S, V>,
267 VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>,
268 AnyAcceptor<S>,
269 AnyForager<S>,
270>;
271
272pub type UnifiedVnd<S, V, DM, IDM> =
273 DynamicVndPhase<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>;
274
275pub fn build_unified_move_selector<S, V, DM, IDM>(
276 config: Option<&MoveSelectorConfig>,
277 descriptor: &SolutionDescriptor,
278 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
279 random_seed: Option<u64>,
280) -> VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>
281where
282 S: PlanningSolution + 'static,
283 V: Clone + PartialEq + Send + Sync + Debug + 'static,
284 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
285 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
286{
287 let mut neighborhoods = Vec::new();
288 collect_neighborhoods(
289 config,
290 descriptor,
291 list_ctx,
292 random_seed,
293 &mut neighborhoods,
294 );
295 assert!(
296 !neighborhoods.is_empty(),
297 "stock move selector configuration produced no neighborhoods"
298 );
299 VecUnionSelector::new(neighborhoods)
300}
301
302fn collect_neighborhoods<S, V, DM, IDM>(
303 config: Option<&MoveSelectorConfig>,
304 descriptor: &SolutionDescriptor,
305 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
306 random_seed: Option<u64>,
307 out: &mut Vec<UnifiedNeighborhood<S, V, DM, IDM>>,
308) where
309 S: PlanningSolution + 'static,
310 V: Clone + PartialEq + Send + Sync + Debug + 'static,
311 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
312 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
313{
314 match config {
315 None => {
316 if descriptor_has_bindings(descriptor) {
317 out.push(UnifiedNeighborhood::Standard(
318 build_descriptor_move_selector(None, descriptor),
319 ));
320 }
321 if let Some(list_ctx) = list_ctx {
322 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
323 None,
324 list_ctx,
325 random_seed,
326 )));
327 }
328 }
329 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
330 for child in &union.selectors {
331 collect_neighborhoods(Some(child), descriptor, list_ctx, random_seed, out);
332 }
333 }
334 Some(MoveSelectorConfig::SelectedCountLimitMoveSelector(limit)) => {
335 match selector_family(limit.selector.as_ref()) {
336 SelectorFamily::Standard => out.push(UnifiedNeighborhood::LimitedStandard(
337 SelectedCountLimitMoveSelector::new(
338 build_descriptor_move_selector(Some(limit.selector.as_ref()), descriptor),
339 limit.selected_count_limit,
340 ),
341 )),
342 SelectorFamily::List => {
343 let Some(list_ctx) = list_ctx else {
344 panic!(
345 "selected_count_limit_move_selector wrapped a list selector in a standard-variable stock context"
346 );
347 };
348 out.push(UnifiedNeighborhood::LimitedList(
349 SelectedCountLimitMoveSelector::new(
350 ListMoveSelectorBuilder::build(
351 Some(limit.selector.as_ref()),
352 list_ctx,
353 random_seed,
354 ),
355 limit.selected_count_limit,
356 ),
357 ));
358 }
359 SelectorFamily::Mixed => {
360 panic!(
361 "selected_count_limit_move_selector cannot wrap a mixed standard/list selector union"
362 );
363 }
364 SelectorFamily::Unsupported => {
365 panic!("cartesian_product move selectors are not supported in stock solving");
366 }
367 }
368 }
369 Some(MoveSelectorConfig::ChangeMoveSelector(_))
370 | Some(MoveSelectorConfig::SwapMoveSelector(_)) => {
371 out.push(UnifiedNeighborhood::Standard(
372 build_descriptor_move_selector(config, descriptor),
373 ));
374 }
375 Some(MoveSelectorConfig::ListChangeMoveSelector(_))
376 | Some(MoveSelectorConfig::NearbyListChangeMoveSelector(_))
377 | Some(MoveSelectorConfig::ListSwapMoveSelector(_))
378 | Some(MoveSelectorConfig::NearbyListSwapMoveSelector(_))
379 | Some(MoveSelectorConfig::SubListChangeMoveSelector(_))
380 | Some(MoveSelectorConfig::SubListSwapMoveSelector(_))
381 | Some(MoveSelectorConfig::ListReverseMoveSelector(_))
382 | Some(MoveSelectorConfig::KOptMoveSelector(_))
383 | Some(MoveSelectorConfig::ListRuinMoveSelector(_)) => {
384 let Some(list_ctx) = list_ctx else {
385 panic!("list move selector configured against a standard-variable stock context");
386 };
387 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
388 config,
389 list_ctx,
390 random_seed,
391 )));
392 }
393 Some(MoveSelectorConfig::CartesianProductMoveSelector(_)) => {
394 panic!("cartesian_product move selectors are not supported in stock solving");
395 }
396 }
397}
398
399pub fn build_unified_local_search<S, V, DM, IDM>(
400 config: Option<&LocalSearchConfig>,
401 descriptor: &SolutionDescriptor,
402 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
403 random_seed: Option<u64>,
404) -> UnifiedLocalSearch<S, V, DM, IDM>
405where
406 S: PlanningSolution + 'static,
407 S::Score: Score + ParseableScore,
408 V: Clone + PartialEq + Send + Sync + Debug + 'static,
409 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
410 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
411{
412 let acceptor = config
413 .and_then(|ls| ls.acceptor.as_ref())
414 .map(|cfg| AcceptorBuilder::build_with_seed::<S>(cfg, random_seed))
415 .unwrap_or_else(|| {
416 if list_ctx.is_some() {
417 AnyAcceptor::LateAcceptance(
418 crate::phase::localsearch::LateAcceptanceAcceptor::<S>::new(400),
419 )
420 } else {
421 match random_seed {
422 Some(seed) => AnyAcceptor::SimulatedAnnealing(
423 SimulatedAnnealingAcceptor::auto_calibrate_with_seed(0.999985, seed),
424 ),
425 None => AnyAcceptor::SimulatedAnnealing(SimulatedAnnealingAcceptor::default()),
426 }
427 }
428 });
429 let forager = config
430 .and_then(|ls| ls.forager.as_ref())
431 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
432 .unwrap_or_else(|| {
433 let accepted = if list_ctx.is_some() { 4 } else { 1 };
434 AnyForager::AcceptedCount(AcceptedCountForager::new(accepted))
435 });
436 let move_selector = build_unified_move_selector(
437 config.and_then(|ls| ls.move_selector.as_ref()),
438 descriptor,
439 list_ctx,
440 random_seed,
441 );
442
443 LocalSearchPhase::new(move_selector, acceptor, forager, None)
444}
445
446pub fn build_unified_vnd<S, V, DM, IDM>(
447 config: &VndConfig,
448 descriptor: &SolutionDescriptor,
449 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
450 random_seed: Option<u64>,
451) -> UnifiedVnd<S, V, DM, IDM>
452where
453 S: PlanningSolution + 'static,
454 S::Score: Score + ParseableScore,
455 V: Clone + PartialEq + Send + Sync + Debug + 'static,
456 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
457 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
458{
459 let neighborhoods = if config.neighborhoods.is_empty() {
460 let mut neighborhoods = Vec::new();
461 collect_neighborhoods(None, descriptor, list_ctx, random_seed, &mut neighborhoods);
462 neighborhoods
463 } else {
464 config
465 .neighborhoods
466 .iter()
467 .flat_map(|selector| {
468 let mut neighborhoods = Vec::new();
469 collect_neighborhoods(
470 Some(selector),
471 descriptor,
472 list_ctx,
473 random_seed,
474 &mut neighborhoods,
475 );
476 neighborhoods
477 })
478 .collect()
479 };
480
481 DynamicVndPhase::new(neighborhoods)
482}