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 + 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 + 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 + 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 + 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 + 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 + 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, descriptor, list_ctx,
307 )));
308 return PhaseSequence::new(phases);
309 }
310
311 for phase in &config.phases {
312 match phase {
313 PhaseConfig::ConstructionHeuristic(ch) => {
314 phases.push(build_construction_phase(
315 ch,
316 descriptor,
317 list_construction.as_ref(),
318 list_variable_name,
319 ));
320 }
321 PhaseConfig::LocalSearch(ls) => {
322 phases.push(RuntimePhase::LocalSearch(build_unified_local_search(
323 Some(ls),
324 descriptor,
325 list_ctx,
326 )));
327 }
328 PhaseConfig::Vnd(vnd) => {
329 phases.push(RuntimePhase::Vnd(build_unified_vnd(
330 vnd, descriptor, list_ctx,
331 )));
332 }
333 _ => {
334 panic!("unsupported phase in the unified runtime");
335 }
336 }
337 }
338
339 PhaseSequence::new(phases)
340}
341
342fn default_construction_phase<S, V, DM, IDM>(
343 descriptor: &SolutionDescriptor,
344 list_construction: Option<&ListConstructionArgs<S, V>>,
345 list_variable_name: Option<&'static str>,
346) -> UnifiedRuntimePhase<S, V, DM, IDM>
347where
348 S: PlanningSolution + 'static,
349 S::Score: Score + ParseableScore,
350 V: Clone + Copy + PartialEq + Eq + Hash + Send + Sync + Debug + 'static,
351 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
352 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
353{
354 RuntimePhase::Construction(UnifiedConstruction::new(
355 None,
356 descriptor.clone(),
357 list_construction.copied(),
358 list_variable_name,
359 ))
360}
361
362fn build_construction_phase<S, V, DM, IDM>(
363 config: &ConstructionHeuristicConfig,
364 descriptor: &SolutionDescriptor,
365 list_construction: Option<&ListConstructionArgs<S, V>>,
366 list_variable_name: Option<&'static str>,
367) -> UnifiedRuntimePhase<S, V, DM, IDM>
368where
369 S: PlanningSolution + 'static,
370 S::Score: Score + ParseableScore,
371 V: Clone + Copy + PartialEq + Eq + Hash + Send + Sync + Debug + 'static,
372 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
373 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
374{
375 RuntimePhase::Construction(UnifiedConstruction::new(
376 Some(config.clone()),
377 descriptor.clone(),
378 list_construction.copied(),
379 list_variable_name,
380 ))
381}
382
383fn list_work_remaining<S, V>(args: &ListConstructionArgs<S, V>, solution: &S) -> bool
384where
385 S: PlanningSolution,
386 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
387{
388 (args.assigned_elements)(solution).len() < (args.element_count)(solution)
389}
390
391fn has_explicit_target(config: &ConstructionHeuristicConfig) -> bool {
392 config.target.variable_name.is_some() || config.target.entity_class.is_some()
393}
394
395fn is_list_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
396 matches!(
397 heuristic,
398 ConstructionHeuristicType::ListRoundRobin
399 | ConstructionHeuristicType::ListCheapestInsertion
400 | ConstructionHeuristicType::ListRegretInsertion
401 | ConstructionHeuristicType::ListClarkeWright
402 | ConstructionHeuristicType::ListKOpt
403 )
404}
405
406fn is_standard_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
407 matches!(
408 heuristic,
409 ConstructionHeuristicType::FirstFitDecreasing
410 | ConstructionHeuristicType::WeakestFit
411 | ConstructionHeuristicType::WeakestFitDecreasing
412 | ConstructionHeuristicType::StrongestFit
413 | ConstructionHeuristicType::StrongestFitDecreasing
414 | ConstructionHeuristicType::AllocateEntityFromQueue
415 | ConstructionHeuristicType::AllocateToValueFromQueue
416 )
417}
418
419fn list_target_matches<S, V>(
420 config: &ConstructionHeuristicConfig,
421 descriptor: &SolutionDescriptor,
422 list_construction: Option<&ListConstructionArgs<S, V>>,
423 list_variable_name: Option<&'static str>,
424) -> bool
425where
426 S: PlanningSolution,
427 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
428{
429 if !has_explicit_target(config) {
430 return false;
431 }
432
433 let Some(list_variable_name) = list_variable_name else {
434 return false;
435 };
436 let Some(list_construction) = list_construction else {
437 return false;
438 };
439 let Some(list_entity_name) = descriptor
440 .entity_descriptors
441 .get(list_construction.descriptor_index)
442 .map(|entity| entity.type_name)
443 else {
444 return false;
445 };
446
447 config
448 .target
449 .variable_name
450 .as_deref()
451 .is_none_or(|name| name == list_variable_name)
452 && config
453 .target
454 .entity_class
455 .as_deref()
456 .is_none_or(|name| name == list_entity_name)
457}
458
459fn normalize_list_construction_config(
460 config: Option<&ConstructionHeuristicConfig>,
461) -> Option<ConstructionHeuristicConfig> {
462 let mut config = config.cloned()?;
463 config.construction_heuristic_type = match config.construction_heuristic_type {
464 ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
465 ConstructionHeuristicType::ListCheapestInsertion
466 }
467 other => other,
468 };
469 Some(config)
470}
471
472#[cfg(test)]
473mod tests {
474 use super::*;
475 use solverforge_config::VariableTargetConfig;
476 use solverforge_core::domain::{EntityDescriptor, VariableDescriptor, VariableType};
477 use std::any::TypeId;
478
479 #[derive(Clone, Debug)]
480 struct TestSolution {
481 score: Option<solverforge_core::score::SoftScore>,
482 }
483
484 impl PlanningSolution for TestSolution {
485 type Score = solverforge_core::score::SoftScore;
486
487 fn score(&self) -> Option<Self::Score> {
488 self.score
489 }
490
491 fn set_score(&mut self, score: Option<Self::Score>) {
492 self.score = score;
493 }
494 }
495
496 fn standard_variable(name: &'static str) -> VariableDescriptor {
497 VariableDescriptor {
498 name,
499 variable_type: VariableType::Genuine,
500 allows_unassigned: true,
501 value_range_provider: Some("values"),
502 value_range_type: solverforge_core::domain::ValueRangeType::Collection,
503 source_variable: None,
504 source_entity: None,
505 usize_getter: Some(|_| None),
506 usize_setter: Some(|_, _| {}),
507 entity_value_provider: Some(|_| vec![1]),
508 }
509 }
510
511 fn descriptor() -> SolutionDescriptor {
512 SolutionDescriptor::new("TestSolution", TypeId::of::<TestSolution>())
513 .with_entity(
514 EntityDescriptor::new("Route", TypeId::of::<()>(), "routes")
515 .with_variable(standard_variable("vehicle_id"))
516 .with_variable(VariableDescriptor::list("visits")),
517 )
518 .with_entity(
519 EntityDescriptor::new("Shift", TypeId::of::<u8>(), "shifts")
520 .with_variable(standard_variable("employee_id")),
521 )
522 }
523
524 fn list_args() -> ListConstructionArgs<TestSolution, usize> {
525 ListConstructionArgs {
526 element_count: |_| 0,
527 assigned_elements: |_| Vec::new(),
528 entity_count: |_| 0,
529 list_len: |_, _| 0,
530 list_insert: |_, _, _, _| {},
531 list_remove: |_, _, _| 0,
532 index_to_element: |_, _| 0,
533 descriptor_index: 0,
534 depot_fn: None,
535 distance_fn: None,
536 element_load_fn: None,
537 capacity_fn: None,
538 assign_route_fn: None,
539 merge_feasible_fn: None,
540 k_opt_get_route: None,
541 k_opt_set_route: None,
542 k_opt_depot_fn: None,
543 k_opt_distance_fn: None,
544 k_opt_feasible_fn: None,
545 }
546 }
547
548 fn config(
549 construction_heuristic_type: ConstructionHeuristicType,
550 entity_class: Option<&str>,
551 variable_name: Option<&str>,
552 ) -> ConstructionHeuristicConfig {
553 ConstructionHeuristicConfig {
554 construction_heuristic_type,
555 target: VariableTargetConfig {
556 entity_class: entity_class.map(str::to_owned),
557 variable_name: variable_name.map(str::to_owned),
558 },
559 k: 2,
560 termination: None,
561 }
562 }
563
564 #[test]
565 fn list_target_requires_matching_variable_name() {
566 let descriptor = descriptor();
567 let cfg = config(
568 ConstructionHeuristicType::ListCheapestInsertion,
569 Some("Shift"),
570 Some("employee_id"),
571 );
572 assert!(!list_target_matches(
573 &cfg,
574 &descriptor,
575 Some(&list_args()),
576 Some("visits")
577 ));
578 }
579
580 #[test]
581 fn list_target_matches_entity_class_only_for_owner() {
582 let descriptor = descriptor();
583 let cfg = config(
584 ConstructionHeuristicType::ListCheapestInsertion,
585 Some("Route"),
586 None,
587 );
588 assert!(list_target_matches(
589 &cfg,
590 &descriptor,
591 Some(&list_args()),
592 Some("visits")
593 ));
594 }
595
596 #[test]
597 fn generic_list_dispatch_normalizes_to_list_cheapest_insertion() {
598 let cfg = config(
599 ConstructionHeuristicType::FirstFit,
600 Some("Route"),
601 Some("visits"),
602 );
603 let normalized = normalize_list_construction_config(Some(&cfg))
604 .expect("generic list config should normalize");
605 assert_eq!(
606 normalized.construction_heuristic_type,
607 ConstructionHeuristicType::ListCheapestInsertion
608 );
609 }
610
611 #[test]
612 fn standard_target_matches_entity_class_only_target() {
613 let descriptor = descriptor();
614 assert!(standard_target_matches(&descriptor, Some("Route"), None,));
615 }
616}