1use std::fmt::{self, Debug};
2use std::hash::Hash;
3use std::marker::PhantomData;
4
5use solverforge_config::{
6 ConstructionHeuristicConfig, ConstructionHeuristicType, PhaseConfig, SolverConfig,
7};
8use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
9use solverforge_core::score::{ParseableScore, Score};
10
11use crate::builder::{build_local_search, build_vnd, LocalSearch, ModelContext, Vnd};
12use crate::descriptor_standard::{
13 build_descriptor_construction, standard_work_remaining_with_frontier,
14};
15use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
16use crate::manager::solve_specialized_list_construction;
17use crate::phase::{sequence::PhaseSequence, Phase};
18use crate::scope::{ProgressCallback, SolverScope};
19
20#[cfg(test)]
21#[path = "runtime_tests.rs"]
22mod tests;
23
24#[cfg(test)]
25#[path = "list_solver_tests.rs"]
26mod list_tests;
27
28pub struct ListVariableMetadata<S, DM, IDM> {
29 pub cross_distance_meter: DM,
30 pub intra_distance_meter: IDM,
31 pub merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
32 pub cw_depot_fn: Option<fn(&S) -> usize>,
33 pub cw_distance_fn: Option<fn(&S, usize, usize) -> i64>,
34 pub cw_element_load_fn: Option<fn(&S, usize) -> i64>,
35 pub cw_capacity_fn: Option<fn(&S) -> i64>,
36 pub cw_assign_route_fn: Option<fn(&mut S, usize, Vec<usize>)>,
37 pub k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
38 pub k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
39 pub k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
40 pub k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
41 pub k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
42 _phantom: PhantomData<fn() -> S>,
43}
44
45pub trait ListVariableEntity<S> {
46 type CrossDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug;
47 type IntraDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug + 'static;
48
49 const HAS_LIST_VARIABLE: bool;
50 const LIST_VARIABLE_NAME: &'static str;
51 const LIST_ELEMENT_SOURCE: Option<&'static str>;
52
53 fn list_field(entity: &Self) -> &[usize];
54 fn list_field_mut(entity: &mut Self) -> &mut Vec<usize>;
55 fn list_metadata() -> ListVariableMetadata<S, Self::CrossDistanceMeter, Self::IntraDistanceMeter>;
56}
57
58impl<S, DM, IDM> ListVariableMetadata<S, DM, IDM> {
59 #[allow(clippy::too_many_arguments)]
60 pub fn new(
61 cross_distance_meter: DM,
62 intra_distance_meter: IDM,
63 merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
64 cw_depot_fn: Option<fn(&S) -> usize>,
65 cw_distance_fn: Option<fn(&S, usize, usize) -> i64>,
66 cw_element_load_fn: Option<fn(&S, usize) -> i64>,
67 cw_capacity_fn: Option<fn(&S) -> i64>,
68 cw_assign_route_fn: Option<fn(&mut S, usize, Vec<usize>)>,
69 k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
70 k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
71 k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
72 k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
73 k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
74 ) -> Self {
75 Self {
76 cross_distance_meter,
77 intra_distance_meter,
78 merge_feasible_fn,
79 cw_depot_fn,
80 cw_distance_fn,
81 cw_element_load_fn,
82 cw_capacity_fn,
83 cw_assign_route_fn,
84 k_opt_get_route,
85 k_opt_set_route,
86 k_opt_depot_fn,
87 k_opt_distance_fn,
88 k_opt_feasible_fn,
89 _phantom: PhantomData,
90 }
91 }
92}
93
94fn has_explicit_target(config: &ConstructionHeuristicConfig) -> bool {
95 config.target.variable_name.is_some() || config.target.entity_class.is_some()
96}
97
98fn is_list_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
99 matches!(
100 heuristic,
101 ConstructionHeuristicType::ListRoundRobin
102 | ConstructionHeuristicType::ListCheapestInsertion
103 | ConstructionHeuristicType::ListRegretInsertion
104 | ConstructionHeuristicType::ListClarkeWright
105 | ConstructionHeuristicType::ListKOpt
106 )
107}
108
109fn is_standard_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
110 matches!(
111 heuristic,
112 ConstructionHeuristicType::FirstFitDecreasing
113 | ConstructionHeuristicType::WeakestFit
114 | ConstructionHeuristicType::WeakestFitDecreasing
115 | ConstructionHeuristicType::StrongestFit
116 | ConstructionHeuristicType::StrongestFitDecreasing
117 | ConstructionHeuristicType::AllocateEntityFromQueue
118 | ConstructionHeuristicType::AllocateToValueFromQueue
119 )
120}
121
122fn should_use_descriptor_standard_path(
123 heuristic: ConstructionHeuristicType,
124 has_matching_scalar: bool,
125 has_matching_list: bool,
126) -> bool {
127 has_matching_scalar && (!has_matching_list || is_standard_only_heuristic(heuristic))
128}
129
130fn matching_list_variables<S, V, DM, IDM>(
131 config: Option<&ConstructionHeuristicConfig>,
132 model: &ModelContext<S, V, DM, IDM>,
133) -> Vec<crate::builder::ListVariableContext<S, V, DM, IDM>>
134where
135 S: PlanningSolution,
136 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
137 DM: Clone,
138 IDM: Clone,
139{
140 let entity_class = config.and_then(|cfg| cfg.target.entity_class.as_deref());
141 let variable_name = config.and_then(|cfg| cfg.target.variable_name.as_deref());
142 let explicit_target = config.is_some_and(has_explicit_target);
143
144 model
145 .list_variables()
146 .filter(|ctx| !explicit_target || ctx.matches_target(entity_class, variable_name))
147 .cloned()
148 .collect()
149}
150
151fn has_matching_scalar_target<S, V, DM, IDM>(
152 config: Option<&ConstructionHeuristicConfig>,
153 model: &ModelContext<S, V, DM, IDM>,
154) -> bool
155where
156 S: PlanningSolution,
157{
158 let entity_class = config.and_then(|cfg| cfg.target.entity_class.as_deref());
159 let variable_name = config.and_then(|cfg| cfg.target.variable_name.as_deref());
160 let explicit_target = config.is_some_and(has_explicit_target);
161
162 model
163 .scalar_variables()
164 .any(|ctx| !explicit_target || ctx.matches_target(entity_class, variable_name))
165}
166
167pub struct Construction<S, V, DM, IDM>
168where
169 S: PlanningSolution,
170 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
171 DM: Clone + Debug + Send + 'static,
172 IDM: Clone + Debug + Send + 'static,
173{
174 config: Option<ConstructionHeuristicConfig>,
175 descriptor: SolutionDescriptor,
176 model: ModelContext<S, V, DM, IDM>,
177}
178
179impl<S, V, DM, IDM> Construction<S, V, DM, IDM>
180where
181 S: PlanningSolution,
182 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
183 DM: Clone + Debug + Send + 'static,
184 IDM: Clone + Debug + Send + 'static,
185{
186 fn new(
187 config: Option<ConstructionHeuristicConfig>,
188 descriptor: SolutionDescriptor,
189 model: ModelContext<S, V, DM, IDM>,
190 ) -> Self {
191 Self {
192 config,
193 descriptor,
194 model,
195 }
196 }
197
198 fn solve_list<D, ProgressCb>(
199 &self,
200 solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
201 list_variables: &[crate::builder::ListVariableContext<S, V, DM, IDM>],
202 ) -> bool
203 where
204 D: solverforge_scoring::Director<S>,
205 ProgressCb: ProgressCallback<S>,
206 {
207 let Some(config) = self.config.as_ref() else {
208 panic!("specialized list construction requires explicit configuration");
209 };
210 if list_variables.is_empty() {
211 panic!("list construction configured against a scalar-only context");
212 }
213
214 solve_specialized_list_construction(
215 config.construction_heuristic_type,
216 config.k,
217 solver_scope,
218 list_variables,
219 )
220 }
221}
222
223impl<S, V, DM, IDM> Debug for Construction<S, V, DM, IDM>
224where
225 S: PlanningSolution,
226 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
227 DM: Clone + Debug + Send + 'static,
228 IDM: Clone + Debug + Send + 'static,
229{
230 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
231 f.debug_struct("Construction")
232 .field("config", &self.config)
233 .field("variable_count", &self.model.variables().len())
234 .finish()
235 }
236}
237
238impl<S, V, DM, IDM, D, ProgressCb> Phase<S, D, ProgressCb> for Construction<S, V, DM, IDM>
239where
240 S: PlanningSolution + 'static,
241 S::Score: Score + Copy,
242 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
243 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
244 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
245 D: solverforge_scoring::Director<S>,
246 ProgressCb: ProgressCallback<S>,
247{
248 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
249 let config = self.config.as_ref();
250 let heuristic = config
251 .map(|cfg| cfg.construction_heuristic_type)
252 .unwrap_or(ConstructionHeuristicType::FirstFit);
253 let list_variables = matching_list_variables(config, &self.model);
254 let has_matching_scalar = has_matching_scalar_target(config, &self.model);
255 let has_matching_list = !list_variables.is_empty();
256 let explicit_target = config.is_some_and(has_explicit_target);
257
258 if is_list_only_heuristic(heuristic) {
259 assert!(
260 self.model.has_list_variables(),
261 "list construction heuristic {:?} configured against a solution with no planning list variable",
262 heuristic
263 );
264 assert!(
265 !explicit_target || !list_variables.is_empty(),
266 "list construction heuristic {:?} does not match the targeted planning list variable for entity_class={:?} variable_name={:?}",
267 heuristic,
268 config.and_then(|cfg| cfg.target.entity_class.as_deref()),
269 config.and_then(|cfg| cfg.target.variable_name.as_deref()),
270 );
271
272 let ran_child_phase = self.solve_list(solver_scope, &list_variables);
273 if !ran_child_phase {
274 finalize_noop_construction(solver_scope);
275 }
276 return;
277 }
278
279 if should_use_descriptor_standard_path(heuristic, has_matching_scalar, has_matching_list) {
280 assert!(
281 !explicit_target || has_matching_scalar,
282 "standard construction heuristic {:?} does not match targeted standard planning variables for entity_class={:?} variable_name={:?}",
283 heuristic,
284 config.and_then(|cfg| cfg.target.entity_class.as_deref()),
285 config.and_then(|cfg| cfg.target.variable_name.as_deref()),
286 );
287 let standard_remaining = standard_work_remaining_with_frontier(
288 &self.descriptor,
289 solver_scope.construction_frontier(),
290 solver_scope.solution_revision(),
291 if explicit_target {
292 config.and_then(|cfg| cfg.target.entity_class.as_deref())
293 } else {
294 None
295 },
296 if explicit_target {
297 config.and_then(|cfg| cfg.target.variable_name.as_deref())
298 } else {
299 None
300 },
301 solver_scope.working_solution(),
302 );
303 if standard_remaining {
304 build_descriptor_construction(config, &self.descriptor).solve(solver_scope);
305 } else {
306 finalize_noop_construction(solver_scope);
307 }
308 return;
309 }
310
311 let ran_child_phase =
312 crate::phase::construction::solve_construction(config, &self.model, solver_scope);
313 if !ran_child_phase {
314 finalize_noop_construction(solver_scope);
315 }
316 }
317
318 fn phase_type_name(&self) -> &'static str {
319 "Construction"
320 }
321}
322
323fn finalize_noop_construction<S, D, ProgressCb>(
324 solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
325) where
326 S: PlanningSolution,
327 D: solverforge_scoring::Director<S>,
328 ProgressCb: ProgressCallback<S>,
329{
330 let had_best = solver_scope.best_score().is_some();
331 solver_scope.update_best_solution();
332 if had_best {
333 solver_scope.promote_current_solution_on_score_tie();
334 }
335}
336
337pub enum RuntimePhase<C, LS, VND> {
338 Construction(C),
339 LocalSearch(LS),
340 Vnd(VND),
341}
342
343impl<C, LS, VND> Debug for RuntimePhase<C, LS, VND>
344where
345 C: Debug,
346 LS: Debug,
347 VND: Debug,
348{
349 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
350 match self {
351 Self::Construction(phase) => write!(f, "RuntimePhase::Construction({phase:?})"),
352 Self::LocalSearch(phase) => write!(f, "RuntimePhase::LocalSearch({phase:?})"),
353 Self::Vnd(phase) => write!(f, "RuntimePhase::Vnd({phase:?})"),
354 }
355 }
356}
357
358impl<S, D, ProgressCb, C, LS, VND> Phase<S, D, ProgressCb> for RuntimePhase<C, LS, VND>
359where
360 S: PlanningSolution,
361 D: solverforge_scoring::Director<S>,
362 ProgressCb: ProgressCallback<S>,
363 C: Phase<S, D, ProgressCb> + Debug,
364 LS: Phase<S, D, ProgressCb> + Debug,
365 VND: Phase<S, D, ProgressCb> + Debug,
366{
367 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
368 match self {
369 Self::Construction(phase) => phase.solve(solver_scope),
370 Self::LocalSearch(phase) => phase.solve(solver_scope),
371 Self::Vnd(phase) => phase.solve(solver_scope),
372 }
373 }
374
375 fn phase_type_name(&self) -> &'static str {
376 "RuntimePhase"
377 }
378}
379
380pub fn build_phases<S, V, DM, IDM>(
381 config: &SolverConfig,
382 descriptor: &SolutionDescriptor,
383 model: &ModelContext<S, V, DM, IDM>,
384) -> PhaseSequence<
385 RuntimePhase<Construction<S, V, DM, IDM>, LocalSearch<S, V, DM, IDM>, Vnd<S, V, DM, IDM>>,
386>
387where
388 S: PlanningSolution + 'static,
389 S::Score: Score + ParseableScore,
390 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
391 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
392 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
393{
394 let mut phases = Vec::new();
395
396 if config.phases.is_empty() {
397 phases.push(RuntimePhase::Construction(Construction::new(
398 None,
399 descriptor.clone(),
400 model.clone(),
401 )));
402 phases.push(RuntimePhase::LocalSearch(build_local_search(
403 None,
404 model,
405 config.random_seed,
406 )));
407 return PhaseSequence::new(phases);
408 }
409
410 for phase in &config.phases {
411 match phase {
412 PhaseConfig::ConstructionHeuristic(ch) => {
413 phases.push(RuntimePhase::Construction(Construction::new(
414 Some(ch.clone()),
415 descriptor.clone(),
416 model.clone(),
417 )));
418 }
419 PhaseConfig::LocalSearch(ls) => {
420 phases.push(RuntimePhase::LocalSearch(build_local_search(
421 Some(ls),
422 model,
423 config.random_seed,
424 )));
425 }
426 PhaseConfig::Vnd(vnd) => {
427 phases.push(RuntimePhase::Vnd(build_vnd(vnd, model, config.random_seed)));
428 }
429 _ => {
430 panic!("unsupported phase in the runtime");
431 }
432 }
433 }
434
435 PhaseSequence::new(phases)
436}
437
438#[cfg(test)]
439mod construction_routing_tests {
440 use super::should_use_descriptor_standard_path;
441 use solverforge_config::ConstructionHeuristicType;
442
443 #[test]
444 fn pure_scalar_first_fit_uses_descriptor_standard_path() {
445 assert!(should_use_descriptor_standard_path(
446 ConstructionHeuristicType::FirstFit,
447 true,
448 false,
449 ));
450 }
451
452 #[test]
453 fn pure_scalar_cheapest_insertion_uses_descriptor_standard_path() {
454 assert!(should_use_descriptor_standard_path(
455 ConstructionHeuristicType::CheapestInsertion,
456 true,
457 false,
458 ));
459 }
460
461 #[test]
462 fn mixed_first_fit_keeps_generic_construction_path() {
463 assert!(!should_use_descriptor_standard_path(
464 ConstructionHeuristicType::FirstFit,
465 true,
466 true,
467 ));
468 }
469
470 #[test]
471 fn mixed_cheapest_insertion_keeps_generic_construction_path() {
472 assert!(!should_use_descriptor_standard_path(
473 ConstructionHeuristicType::CheapestInsertion,
474 true,
475 true,
476 ));
477 }
478
479 #[test]
480 fn standard_only_heuristics_still_route_to_descriptor_path() {
481 assert!(should_use_descriptor_standard_path(
482 ConstructionHeuristicType::StrongestFit,
483 true,
484 true,
485 ));
486 }
487}