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, ModelContext, Vnd};
10use crate::descriptor_scalar::{
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: ModelContext<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: ModelContext<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::ListVariableContext<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 context");
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::DescriptorScalar => {
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::GroupedScalar => {
204 let Some((group_index, group)) = capabilities.scalar_group.as_ref() else {
205 unreachable!("grouped scalar route requires a selected scalar group");
206 };
207 let ran_child_phase = crate::phase::construction::solve_grouped_scalar_construction(
208 config,
209 *group_index,
210 group,
211 &capabilities.scalar_bindings,
212 solver_scope,
213 );
214 if !ran_child_phase {
215 finalize_noop_construction(solver_scope);
216 }
217 }
218 ConstructionRoute::GenericMixed => {
219 let ran_child_phase = crate::phase::construction::solve_construction(
220 config,
221 &self.model,
222 solver_scope,
223 );
224 if !ran_child_phase {
225 finalize_noop_construction(solver_scope);
226 }
227 }
228 }
229 }
230
231 fn phase_type_name(&self) -> &'static str {
232 "Construction"
233 }
234}
235
236fn finalize_noop_construction<S, D, ProgressCb>(
237 solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
238) where
239 S: PlanningSolution,
240 D: solverforge_scoring::Director<S>,
241 ProgressCb: ProgressCallback<S>,
242{
243 let had_best = solver_scope.best_score().is_some();
244 solver_scope.update_best_solution();
245 if had_best {
246 solver_scope.promote_current_solution_on_score_tie();
247 }
248}
249
250pub enum RuntimePhase<C, LS, VND> {
251 Construction(C),
252 LocalSearch(LS),
253 Vnd(VND),
254}
255
256impl<C, LS, VND> Debug for RuntimePhase<C, LS, VND>
257where
258 C: Debug,
259 LS: Debug,
260 VND: Debug,
261{
262 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
263 match self {
264 Self::Construction(phase) => write!(f, "RuntimePhase::Construction({phase:?})"),
265 Self::LocalSearch(phase) => write!(f, "RuntimePhase::LocalSearch({phase:?})"),
266 Self::Vnd(phase) => write!(f, "RuntimePhase::Vnd({phase:?})"),
267 }
268 }
269}
270
271impl<S, D, ProgressCb, C, LS, VND> Phase<S, D, ProgressCb> for RuntimePhase<C, LS, VND>
272where
273 S: PlanningSolution,
274 D: solverforge_scoring::Director<S>,
275 ProgressCb: ProgressCallback<S>,
276 C: Phase<S, D, ProgressCb> + Debug,
277 LS: Phase<S, D, ProgressCb> + Debug,
278 VND: Phase<S, D, ProgressCb> + Debug,
279{
280 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
281 match self {
282 Self::Construction(phase) => phase.solve(solver_scope),
283 Self::LocalSearch(phase) => phase.solve(solver_scope),
284 Self::Vnd(phase) => phase.solve(solver_scope),
285 }
286 }
287
288 fn phase_type_name(&self) -> &'static str {
289 "RuntimePhase"
290 }
291}
292
293pub fn build_phases<S, V, DM, IDM>(
294 config: &SolverConfig,
295 descriptor: &SolutionDescriptor,
296 model: &ModelContext<S, V, DM, IDM>,
297) -> PhaseSequence<
298 RuntimePhase<Construction<S, V, DM, IDM>, LocalSearch<S, V, DM, IDM>, Vnd<S, V, DM, IDM>>,
299>
300where
301 S: PlanningSolution + 'static,
302 S::Score: Score + ParseableScore,
303 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
304 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
305 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
306{
307 let mut phases = Vec::new();
308
309 if config.phases.is_empty() {
310 phases.push(RuntimePhase::Construction(Construction::new(
311 None,
312 descriptor.clone(),
313 model.clone(),
314 )));
315 phases.push(RuntimePhase::LocalSearch(build_local_search(
316 None,
317 model,
318 config.random_seed,
319 )));
320 return PhaseSequence::new(phases);
321 }
322
323 for phase in &config.phases {
324 match phase {
325 PhaseConfig::ConstructionHeuristic(ch) => {
326 phases.push(RuntimePhase::Construction(Construction::new(
327 Some(ch.clone()),
328 descriptor.clone(),
329 model.clone(),
330 )));
331 }
332 PhaseConfig::LocalSearch(ls) => {
333 phases.push(RuntimePhase::LocalSearch(build_local_search(
334 Some(ls),
335 model,
336 config.random_seed,
337 )));
338 }
339 PhaseConfig::Vnd(vnd) => {
340 phases.push(RuntimePhase::Vnd(build_vnd(vnd, model, config.random_seed)));
341 }
342 _ => {
343 panic!("unsupported phase in the runtime");
344 }
345 }
346 }
347
348 PhaseSequence::new(phases)
349}
350
351#[cfg(test)]
352mod construction_routing_tests {
353 use solverforge_config::ConstructionHeuristicType;
354
355 fn should_use_descriptor_scalar_path(
356 heuristic: ConstructionHeuristicType,
357 has_scalar_variables: bool,
358 has_list_variables: bool,
359 ) -> bool {
360 if !has_scalar_variables {
361 return false;
362 }
363
364 match heuristic {
365 ConstructionHeuristicType::ListRoundRobin
366 | ConstructionHeuristicType::ListCheapestInsertion
367 | ConstructionHeuristicType::ListRegretInsertion
368 | ConstructionHeuristicType::ListClarkeWright
369 | ConstructionHeuristicType::ListKOpt => false,
370 ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
371 !has_list_variables
372 }
373 ConstructionHeuristicType::FirstFitDecreasing
374 | ConstructionHeuristicType::WeakestFit
375 | ConstructionHeuristicType::WeakestFitDecreasing
376 | ConstructionHeuristicType::StrongestFit
377 | ConstructionHeuristicType::StrongestFitDecreasing
378 | ConstructionHeuristicType::AllocateEntityFromQueue
379 | ConstructionHeuristicType::AllocateToValueFromQueue => true,
380 }
381 }
382
383 #[test]
384 fn pure_scalar_first_fit_uses_descriptor_scalar_path() {
385 assert!(should_use_descriptor_scalar_path(
386 ConstructionHeuristicType::FirstFit,
387 true,
388 false,
389 ));
390 }
391
392 #[test]
393 fn pure_scalar_cheapest_insertion_uses_descriptor_scalar_path() {
394 assert!(should_use_descriptor_scalar_path(
395 ConstructionHeuristicType::CheapestInsertion,
396 true,
397 false,
398 ));
399 }
400
401 #[test]
402 fn mixed_first_fit_keeps_generic_construction_path() {
403 assert!(!should_use_descriptor_scalar_path(
404 ConstructionHeuristicType::FirstFit,
405 true,
406 true,
407 ));
408 }
409
410 #[test]
411 fn mixed_cheapest_insertion_keeps_generic_construction_path() {
412 assert!(!should_use_descriptor_scalar_path(
413 ConstructionHeuristicType::CheapestInsertion,
414 true,
415 true,
416 ));
417 }
418
419 #[test]
420 fn scalar_only_heuristics_still_route_to_descriptor_path() {
421 assert!(should_use_descriptor_scalar_path(
422 ConstructionHeuristicType::StrongestFit,
423 true,
424 true,
425 ));
426 }
427}