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