1use std::fmt::{self, Debug};
2use std::hash::Hash;
3
4use solverforge_config::{
5 ConstructionHeuristicConfig, ConstructionHeuristicType, PhaseConfig, SolverConfig,
6};
7use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
8use solverforge_core::score::{ParseableScore, Score};
9
10use crate::builder::ListContext;
11use crate::descriptor_standard::{
12 build_descriptor_construction, standard_target_matches, standard_work_remaining,
13};
14use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
15use crate::list_solver::build_list_construction;
16use crate::phase::{sequence::PhaseSequence, Phase};
17use crate::scope::{ProgressCallback, SolverScope};
18use crate::unified_search::{
19 build_unified_local_search, build_unified_vnd, UnifiedLocalSearch, UnifiedVnd,
20};
21
22pub struct UnifiedConstruction<S, V>
23where
24 S: PlanningSolution,
25 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + 'static,
26{
27 config: Option<ConstructionHeuristicConfig>,
28 descriptor: SolutionDescriptor,
29 list_construction: Option<ListConstructionArgs<S, V>>,
30 list_variable_name: Option<&'static str>,
31}
32
33impl<S, V> UnifiedConstruction<S, V>
34where
35 S: PlanningSolution,
36 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + 'static,
37{
38 fn new(
39 config: Option<ConstructionHeuristicConfig>,
40 descriptor: SolutionDescriptor,
41 list_construction: Option<ListConstructionArgs<S, V>>,
42 list_variable_name: Option<&'static str>,
43 ) -> Self {
44 Self {
45 config,
46 descriptor,
47 list_construction,
48 list_variable_name,
49 }
50 }
51}
52
53impl<S, V> Debug for UnifiedConstruction<S, V>
54where
55 S: PlanningSolution,
56 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
57{
58 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59 f.debug_struct("UnifiedConstruction")
60 .field("config", &self.config)
61 .field("has_list_construction", &self.list_construction.is_some())
62 .field("list_variable_name", &self.list_variable_name)
63 .finish()
64 }
65}
66
67impl<S, V, D, ProgressCb> Phase<S, D, ProgressCb> for UnifiedConstruction<S, V>
68where
69 S: PlanningSolution + 'static,
70 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
71 D: solverforge_scoring::Director<S>,
72 ProgressCb: ProgressCallback<S>,
73{
74 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
75 let config = self.config.as_ref();
76 let explicit_target = config.is_some_and(has_explicit_target);
77 let entity_class = config.and_then(|cfg| cfg.target.entity_class.as_deref());
78 let variable_name = config.and_then(|cfg| cfg.target.variable_name.as_deref());
79 let standard_matches = config.is_some_and(|_| {
80 standard_target_matches(&self.descriptor, entity_class, variable_name)
81 });
82 let list_matches = config.is_some_and(|cfg| {
83 list_target_matches(
84 cfg,
85 &self.descriptor,
86 self.list_construction.as_ref(),
87 self.list_variable_name,
88 )
89 });
90
91 if let Some(cfg) = config {
92 if explicit_target && !standard_matches && !list_matches {
93 panic!(
94 "construction heuristic matched no planning variables for entity_class={:?} variable_name={:?}",
95 cfg.target.entity_class,
96 cfg.target.variable_name
97 );
98 }
99
100 let heuristic = cfg.construction_heuristic_type;
101 if is_list_only_heuristic(heuristic) {
102 assert!(
103 self.list_construction.is_some(),
104 "list construction heuristic {:?} configured against a solution with no planning list variable",
105 heuristic
106 );
107 assert!(
108 !explicit_target || list_matches,
109 "list construction heuristic {:?} does not match the targeted planning list variable for entity_class={:?} variable_name={:?}",
110 heuristic,
111 cfg.target.entity_class,
112 cfg.target.variable_name
113 );
114 self.solve_list(solver_scope);
115 return;
116 }
117
118 if is_standard_only_heuristic(heuristic) {
119 assert!(
120 !explicit_target || standard_matches,
121 "standard construction heuristic {:?} does not match targeted standard planning variables for entity_class={:?} variable_name={:?}",
122 heuristic,
123 cfg.target.entity_class,
124 cfg.target.variable_name
125 );
126 build_descriptor_construction(Some(cfg), &self.descriptor).solve(solver_scope);
127 return;
128 }
129 }
130
131 if self.list_construction.is_none() {
132 build_descriptor_construction(config, &self.descriptor).solve(solver_scope);
133 return;
134 }
135
136 let standard_remaining = standard_work_remaining(
137 &self.descriptor,
138 if explicit_target { entity_class } else { None },
139 if explicit_target { variable_name } else { None },
140 solver_scope.working_solution(),
141 );
142 let list_remaining = self
143 .list_construction
144 .as_ref()
145 .map(|args| {
146 (!explicit_target || list_matches)
147 && list_work_remaining(args, solver_scope.working_solution())
148 })
149 .unwrap_or(false);
150
151 if standard_remaining {
152 build_descriptor_construction(config, &self.descriptor).solve(solver_scope);
153 }
154 if list_remaining {
155 self.solve_list(solver_scope);
156 }
157 }
158
159 fn phase_type_name(&self) -> &'static str {
160 "UnifiedConstruction"
161 }
162}
163
164impl<S, V> UnifiedConstruction<S, V>
165where
166 S: PlanningSolution + 'static,
167 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
168{
169 fn solve_list<D, ProgressCb>(&self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>)
170 where
171 D: solverforge_scoring::Director<S>,
172 ProgressCb: ProgressCallback<S>,
173 {
174 let Some(args) = self.list_construction.as_ref() else {
175 panic!("list construction configured against a standard-variable context");
176 };
177 let normalized = normalize_list_construction_config(self.config.as_ref());
178 build_list_construction(
179 normalized.as_ref(),
180 args.element_count,
181 args.assigned_elements,
182 args.entity_count,
183 args.list_len,
184 args.list_insert,
185 args.list_remove,
186 args.index_to_element,
187 args.descriptor_index,
188 args.depot_fn,
189 args.distance_fn,
190 args.element_load_fn,
191 args.capacity_fn,
192 args.assign_route_fn,
193 args.merge_feasible_fn,
194 args.k_opt_get_route,
195 args.k_opt_set_route,
196 args.k_opt_depot_fn,
197 args.k_opt_distance_fn,
198 args.k_opt_feasible_fn,
199 )
200 .solve(solver_scope);
201 }
202}
203
204pub enum RuntimePhase<C, LS, VND> {
205 Construction(C),
206 LocalSearch(LS),
207 Vnd(VND),
208}
209
210impl<C, LS, VND> Debug for RuntimePhase<C, LS, VND>
211where
212 C: Debug,
213 LS: Debug,
214 VND: Debug,
215{
216 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217 match self {
218 Self::Construction(phase) => write!(f, "RuntimePhase::Construction({phase:?})"),
219 Self::LocalSearch(phase) => write!(f, "RuntimePhase::LocalSearch({phase:?})"),
220 Self::Vnd(phase) => write!(f, "RuntimePhase::Vnd({phase:?})"),
221 }
222 }
223}
224
225impl<S, D, ProgressCb, C, LS, VND> Phase<S, D, ProgressCb> for RuntimePhase<C, LS, VND>
226where
227 S: PlanningSolution,
228 D: solverforge_scoring::Director<S>,
229 ProgressCb: ProgressCallback<S>,
230 C: Phase<S, D, ProgressCb> + Debug,
231 LS: Phase<S, D, ProgressCb> + Debug,
232 VND: Phase<S, D, ProgressCb> + Debug,
233{
234 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
235 match self {
236 Self::Construction(phase) => phase.solve(solver_scope),
237 Self::LocalSearch(phase) => phase.solve(solver_scope),
238 Self::Vnd(phase) => phase.solve(solver_scope),
239 }
240 }
241
242 fn phase_type_name(&self) -> &'static str {
243 "RuntimePhase"
244 }
245}
246
247pub type UnifiedRuntimePhase<S, V, DM, IDM> = RuntimePhase<
248 UnifiedConstruction<S, V>,
249 UnifiedLocalSearch<S, V, DM, IDM>,
250 UnifiedVnd<S, V, DM, IDM>,
251>;
252
253pub struct ListConstructionArgs<S, V> {
254 pub element_count: fn(&S) -> usize,
255 pub assigned_elements: fn(&S) -> Vec<V>,
256 pub entity_count: fn(&S) -> usize,
257 pub list_len: fn(&S, usize) -> usize,
258 pub list_insert: fn(&mut S, usize, usize, V),
259 pub list_remove: fn(&mut S, usize, usize) -> V,
260 pub index_to_element: fn(&S, usize) -> V,
261 pub descriptor_index: usize,
262 pub depot_fn: Option<fn(&S) -> usize>,
263 pub distance_fn: Option<fn(&S, usize, usize) -> i64>,
264 pub element_load_fn: Option<fn(&S, usize) -> i64>,
265 pub capacity_fn: Option<fn(&S) -> i64>,
266 pub assign_route_fn: Option<fn(&mut S, usize, Vec<V>)>,
267 pub merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
268 pub k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
269 pub k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
270 pub k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
271 pub k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
272 pub k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
273}
274
275impl<S, V> Clone for ListConstructionArgs<S, V> {
276 fn clone(&self) -> Self {
277 *self
278 }
279}
280
281impl<S, V> Copy for ListConstructionArgs<S, V> {}
282
283pub fn build_phases<S, V, DM, IDM>(
284 config: &SolverConfig,
285 descriptor: &SolutionDescriptor,
286 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
287 list_construction: Option<ListConstructionArgs<S, V>>,
288 list_variable_name: Option<&'static str>,
289) -> PhaseSequence<UnifiedRuntimePhase<S, V, DM, IDM>>
290where
291 S: PlanningSolution + 'static,
292 S::Score: Score + ParseableScore,
293 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
294 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
295 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
296{
297 let mut phases = Vec::new();
298
299 if config.phases.is_empty() {
300 phases.push(default_construction_phase(
301 descriptor,
302 list_construction.as_ref(),
303 list_variable_name,
304 ));
305 phases.push(RuntimePhase::LocalSearch(build_unified_local_search(
306 None,
307 descriptor,
308 list_ctx,
309 config.random_seed,
310 )));
311 return PhaseSequence::new(phases);
312 }
313
314 for phase in &config.phases {
315 match phase {
316 PhaseConfig::ConstructionHeuristic(ch) => {
317 phases.push(build_construction_phase(
318 ch,
319 descriptor,
320 list_construction.as_ref(),
321 list_variable_name,
322 ));
323 }
324 PhaseConfig::LocalSearch(ls) => {
325 phases.push(RuntimePhase::LocalSearch(build_unified_local_search(
326 Some(ls),
327 descriptor,
328 list_ctx,
329 config.random_seed,
330 )));
331 }
332 PhaseConfig::Vnd(vnd) => {
333 phases.push(RuntimePhase::Vnd(build_unified_vnd(
334 vnd,
335 descriptor,
336 list_ctx,
337 config.random_seed,
338 )));
339 }
340 _ => {
341 panic!("unsupported phase in the unified runtime");
342 }
343 }
344 }
345
346 PhaseSequence::new(phases)
347}
348
349fn default_construction_phase<S, V, DM, IDM>(
350 descriptor: &SolutionDescriptor,
351 list_construction: Option<&ListConstructionArgs<S, V>>,
352 list_variable_name: Option<&'static str>,
353) -> UnifiedRuntimePhase<S, V, DM, IDM>
354where
355 S: PlanningSolution + 'static,
356 S::Score: Score + ParseableScore,
357 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
358 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
359 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
360{
361 RuntimePhase::Construction(UnifiedConstruction::new(
362 None,
363 descriptor.clone(),
364 list_construction.copied(),
365 list_variable_name,
366 ))
367}
368
369fn build_construction_phase<S, V, DM, IDM>(
370 config: &ConstructionHeuristicConfig,
371 descriptor: &SolutionDescriptor,
372 list_construction: Option<&ListConstructionArgs<S, V>>,
373 list_variable_name: Option<&'static str>,
374) -> UnifiedRuntimePhase<S, V, DM, IDM>
375where
376 S: PlanningSolution + 'static,
377 S::Score: Score + ParseableScore,
378 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
379 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
380 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
381{
382 RuntimePhase::Construction(UnifiedConstruction::new(
383 Some(config.clone()),
384 descriptor.clone(),
385 list_construction.copied(),
386 list_variable_name,
387 ))
388}
389
390fn list_work_remaining<S, V>(args: &ListConstructionArgs<S, V>, solution: &S) -> bool
391where
392 S: PlanningSolution,
393 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
394{
395 (args.assigned_elements)(solution).len() < (args.element_count)(solution)
396}
397
398fn has_explicit_target(config: &ConstructionHeuristicConfig) -> bool {
399 config.target.variable_name.is_some() || config.target.entity_class.is_some()
400}
401
402fn is_list_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
403 matches!(
404 heuristic,
405 ConstructionHeuristicType::ListRoundRobin
406 | ConstructionHeuristicType::ListCheapestInsertion
407 | ConstructionHeuristicType::ListRegretInsertion
408 | ConstructionHeuristicType::ListClarkeWright
409 | ConstructionHeuristicType::ListKOpt
410 )
411}
412
413fn is_standard_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
414 matches!(
415 heuristic,
416 ConstructionHeuristicType::FirstFitDecreasing
417 | ConstructionHeuristicType::WeakestFit
418 | ConstructionHeuristicType::WeakestFitDecreasing
419 | ConstructionHeuristicType::StrongestFit
420 | ConstructionHeuristicType::StrongestFitDecreasing
421 | ConstructionHeuristicType::AllocateEntityFromQueue
422 | ConstructionHeuristicType::AllocateToValueFromQueue
423 )
424}
425
426fn list_target_matches<S, V>(
427 config: &ConstructionHeuristicConfig,
428 descriptor: &SolutionDescriptor,
429 list_construction: Option<&ListConstructionArgs<S, V>>,
430 list_variable_name: Option<&'static str>,
431) -> bool
432where
433 S: PlanningSolution,
434 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
435{
436 if !has_explicit_target(config) {
437 return false;
438 }
439
440 let Some(list_variable_name) = list_variable_name else {
441 return false;
442 };
443 let Some(list_construction) = list_construction else {
444 return false;
445 };
446 let Some(list_entity_name) = descriptor
447 .entity_descriptors
448 .get(list_construction.descriptor_index)
449 .map(|entity| entity.type_name)
450 else {
451 return false;
452 };
453
454 config
455 .target
456 .variable_name
457 .as_deref()
458 .is_none_or(|name| name == list_variable_name)
459 && config
460 .target
461 .entity_class
462 .as_deref()
463 .is_none_or(|name| name == list_entity_name)
464}
465
466fn normalize_list_construction_config(
467 config: Option<&ConstructionHeuristicConfig>,
468) -> Option<ConstructionHeuristicConfig> {
469 let mut config = config.cloned()?;
470 config.construction_heuristic_type = match config.construction_heuristic_type {
471 ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
472 ConstructionHeuristicType::ListCheapestInsertion
473 }
474 other => other,
475 };
476 Some(config)
477}
478
479#[cfg(test)]
480mod tests {
481 use super::*;
482 use solverforge_config::VariableTargetConfig;
483 use solverforge_core::domain::{EntityDescriptor, VariableDescriptor, VariableType};
484 use std::any::TypeId;
485
486 #[derive(Clone, Debug)]
487 struct TestSolution {
488 score: Option<solverforge_core::score::SoftScore>,
489 }
490
491 impl PlanningSolution for TestSolution {
492 type Score = solverforge_core::score::SoftScore;
493
494 fn score(&self) -> Option<Self::Score> {
495 self.score
496 }
497
498 fn set_score(&mut self, score: Option<Self::Score>) {
499 self.score = score;
500 }
501 }
502
503 fn standard_variable(name: &'static str) -> VariableDescriptor {
504 VariableDescriptor {
505 name,
506 variable_type: VariableType::Genuine,
507 allows_unassigned: true,
508 value_range_provider: Some("values"),
509 value_range_type: solverforge_core::domain::ValueRangeType::Collection,
510 source_variable: None,
511 source_entity: None,
512 usize_getter: Some(|_| None),
513 usize_setter: Some(|_, _| {}),
514 entity_value_provider: Some(|_| vec![1]),
515 }
516 }
517
518 fn descriptor() -> SolutionDescriptor {
519 SolutionDescriptor::new("TestSolution", TypeId::of::<TestSolution>())
520 .with_entity(
521 EntityDescriptor::new("Route", TypeId::of::<()>(), "routes")
522 .with_variable(standard_variable("vehicle_id"))
523 .with_variable(VariableDescriptor::list("visits")),
524 )
525 .with_entity(
526 EntityDescriptor::new("Shift", TypeId::of::<u8>(), "shifts")
527 .with_variable(standard_variable("employee_id")),
528 )
529 }
530
531 fn list_args() -> ListConstructionArgs<TestSolution, usize> {
532 ListConstructionArgs {
533 element_count: |_| 0,
534 assigned_elements: |_| Vec::new(),
535 entity_count: |_| 0,
536 list_len: |_, _| 0,
537 list_insert: |_, _, _, _| {},
538 list_remove: |_, _, _| 0,
539 index_to_element: |_, _| 0,
540 descriptor_index: 0,
541 depot_fn: None,
542 distance_fn: None,
543 element_load_fn: None,
544 capacity_fn: None,
545 assign_route_fn: None,
546 merge_feasible_fn: None,
547 k_opt_get_route: None,
548 k_opt_set_route: None,
549 k_opt_depot_fn: None,
550 k_opt_distance_fn: None,
551 k_opt_feasible_fn: None,
552 }
553 }
554
555 fn config(
556 construction_heuristic_type: ConstructionHeuristicType,
557 entity_class: Option<&str>,
558 variable_name: Option<&str>,
559 ) -> ConstructionHeuristicConfig {
560 ConstructionHeuristicConfig {
561 construction_heuristic_type,
562 target: VariableTargetConfig {
563 entity_class: entity_class.map(str::to_owned),
564 variable_name: variable_name.map(str::to_owned),
565 },
566 k: 2,
567 termination: None,
568 }
569 }
570
571 #[test]
572 fn list_target_requires_matching_variable_name() {
573 let descriptor = descriptor();
574 let cfg = config(
575 ConstructionHeuristicType::ListCheapestInsertion,
576 Some("Shift"),
577 Some("employee_id"),
578 );
579 assert!(!list_target_matches(
580 &cfg,
581 &descriptor,
582 Some(&list_args()),
583 Some("visits")
584 ));
585 }
586
587 #[test]
588 fn list_target_matches_entity_class_only_for_owner() {
589 let descriptor = descriptor();
590 let cfg = config(
591 ConstructionHeuristicType::ListCheapestInsertion,
592 Some("Route"),
593 None,
594 );
595 assert!(list_target_matches(
596 &cfg,
597 &descriptor,
598 Some(&list_args()),
599 Some("visits")
600 ));
601 }
602
603 #[test]
604 fn generic_list_dispatch_normalizes_to_list_cheapest_insertion() {
605 let cfg = config(
606 ConstructionHeuristicType::FirstFit,
607 Some("Route"),
608 Some("visits"),
609 );
610 let normalized = normalize_list_construction_config(Some(&cfg))
611 .expect("generic list config should normalize");
612 assert_eq!(
613 normalized.construction_heuristic_type,
614 ConstructionHeuristicType::ListCheapestInsertion
615 );
616 }
617
618 #[test]
619 fn standard_target_matches_entity_class_only_target() {
620 let descriptor = descriptor();
621 assert!(standard_target_matches(&descriptor, Some("Route"), None,));
622 }
623}