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