solverforge_solver/
list_solver.rs

1/* List stock helpers for routing and scheduling problems.
2
3This module provides the concrete list construction and local-search
4building blocks used by the unified stock runtime. The solver
5configuration (construction type, move selectors, acceptor, forager,
6termination) is driven by `solver.toml`.
7
8Logging levels:
9- **INFO**: Solver start/end, phase summaries, problem scale
10- **DEBUG**: Individual steps with timing and scores
11- **TRACE**: Move evaluation details
12*/
13
14use solverforge_config::{ConstructionHeuristicConfig, ConstructionHeuristicType};
15use solverforge_core::domain::PlanningSolution;
16use std::fmt;
17use std::marker::PhantomData;
18
19use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
20use crate::manager::{
21    ListCheapestInsertionPhase, ListClarkeWrightPhase, ListKOptPhase, ListRegretInsertionPhase,
22};
23use crate::scope::{PhaseScope, SolverScope, StepScope};
24
25/// Hidden list metadata emitted by `#[planning_entity]` and consumed by
26/// macro-generated solve code.
27pub struct ListVariableMetadata<S, DM, IDM> {
28    pub cross_distance_meter: DM,
29    pub intra_distance_meter: IDM,
30    pub merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
31    pub cw_depot_fn: Option<fn(&S) -> usize>,
32    pub cw_distance_fn: Option<fn(&S, usize, usize) -> i64>,
33    pub cw_element_load_fn: Option<fn(&S, usize) -> i64>,
34    pub cw_capacity_fn: Option<fn(&S) -> i64>,
35    pub cw_assign_route_fn: Option<fn(&mut S, usize, Vec<usize>)>,
36    pub k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
37    pub k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
38    pub k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
39    pub k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
40    pub k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
41    _phantom: PhantomData<fn() -> S>,
42}
43
44/// Hidden trait implemented by `#[planning_entity]` for list-stock entities so
45/// `#[planning_solution]` can consume typed list metadata without re-stating
46/// it on the solution.
47pub trait ListVariableEntity<S> {
48    type CrossDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug;
49    type IntraDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug + 'static;
50
51    const HAS_STOCK_LIST_VARIABLE: bool;
52    const STOCK_LIST_VARIABLE_NAME: &'static str;
53    const STOCK_LIST_ELEMENT_SOURCE: Option<&'static str>;
54
55    fn list_field(entity: &Self) -> &[usize];
56    fn list_field_mut(entity: &mut Self) -> &mut Vec<usize>;
57    fn list_metadata() -> ListVariableMetadata<S, Self::CrossDistanceMeter, Self::IntraDistanceMeter>;
58}
59
60impl<S, DM, IDM> ListVariableMetadata<S, DM, IDM> {
61    #[allow(clippy::too_many_arguments)]
62    pub fn new(
63        cross_distance_meter: DM,
64        intra_distance_meter: IDM,
65        merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
66        cw_depot_fn: Option<fn(&S) -> usize>,
67        cw_distance_fn: Option<fn(&S, usize, usize) -> i64>,
68        cw_element_load_fn: Option<fn(&S, usize) -> i64>,
69        cw_capacity_fn: Option<fn(&S) -> i64>,
70        cw_assign_route_fn: Option<fn(&mut S, usize, Vec<usize>)>,
71        k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
72        k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
73        k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
74        k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
75        k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
76    ) -> Self {
77        Self {
78            cross_distance_meter,
79            intra_distance_meter,
80            merge_feasible_fn,
81            cw_depot_fn,
82            cw_distance_fn,
83            cw_element_load_fn,
84            cw_capacity_fn,
85            cw_assign_route_fn,
86            k_opt_get_route,
87            k_opt_set_route,
88            k_opt_depot_fn,
89            k_opt_distance_fn,
90            k_opt_feasible_fn,
91            _phantom: PhantomData,
92        }
93    }
94}
95
96// Construction phase enum for list solver.
97pub enum ListConstruction<S, V>
98where
99    S: PlanningSolution,
100    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + 'static,
101{
102    RoundRobin(ListRoundRobinPhase<S, V>),
103    CheapestInsertion(ListCheapestInsertionPhase<S, V>),
104    RegretInsertion(ListRegretInsertionPhase<S, V>),
105    ClarkeWright(ListClarkeWrightPhase<S, V>),
106    KOpt(ListKOptPhase<S, V>),
107}
108
109impl<S, V> fmt::Debug for ListConstruction<S, V>
110where
111    S: PlanningSolution,
112    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + fmt::Debug + 'static,
113{
114    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
115        match self {
116            Self::RoundRobin(phase) => write!(f, "ListConstruction::RoundRobin({phase:?})"),
117            Self::CheapestInsertion(phase) => {
118                write!(f, "ListConstruction::CheapestInsertion({phase:?})")
119            }
120            Self::RegretInsertion(phase) => {
121                write!(f, "ListConstruction::RegretInsertion({phase:?})")
122            }
123            Self::ClarkeWright(phase) => {
124                write!(f, "ListConstruction::ClarkeWright({phase:?})")
125            }
126            Self::KOpt(phase) => write!(f, "ListConstruction::KOpt({phase:?})"),
127        }
128    }
129}
130
131impl<S, V, D, ProgressCb> crate::phase::Phase<S, D, ProgressCb> for ListConstruction<S, V>
132where
133    S: PlanningSolution,
134    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + fmt::Debug + 'static,
135    D: solverforge_scoring::Director<S>,
136    ProgressCb: crate::scope::ProgressCallback<S>,
137{
138    fn solve(&mut self, solver_scope: &mut crate::scope::SolverScope<'_, S, D, ProgressCb>) {
139        match self {
140            Self::RoundRobin(phase) => phase.solve(solver_scope),
141            Self::CheapestInsertion(phase) => phase.solve(solver_scope),
142            Self::RegretInsertion(phase) => phase.solve(solver_scope),
143            Self::ClarkeWright(phase) => phase.solve(solver_scope),
144            Self::KOpt(phase) => phase.solve(solver_scope),
145        }
146    }
147
148    fn phase_type_name(&self) -> &'static str {
149        "ListConstruction"
150    }
151}
152
153pub struct ListRoundRobinPhase<S, V>
154where
155    S: PlanningSolution,
156    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + 'static,
157{
158    element_count: fn(&S) -> usize,
159    get_assigned: fn(&S) -> Vec<V>,
160    entity_count: fn(&S) -> usize,
161    list_len: fn(&S, usize) -> usize,
162    list_insert: fn(&mut S, usize, usize, V),
163    index_to_element: fn(&S, usize) -> V,
164    descriptor_index: usize,
165    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
166}
167
168impl<S, V> fmt::Debug for ListRoundRobinPhase<S, V>
169where
170    S: PlanningSolution,
171    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + 'static,
172{
173    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
174        f.debug_struct("ListRoundRobinPhase").finish()
175    }
176}
177
178impl<S, V, D, ProgressCb> crate::phase::Phase<S, D, ProgressCb> for ListRoundRobinPhase<S, V>
179where
180    S: PlanningSolution,
181    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + fmt::Debug + 'static,
182    D: solverforge_scoring::Director<S>,
183    ProgressCb: crate::scope::ProgressCallback<S>,
184{
185    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
186        let mut phase_scope = PhaseScope::new(solver_scope, 0);
187
188        let solution = phase_scope.score_director().working_solution();
189        let n_elements = (self.element_count)(solution);
190        let n_entities = (self.entity_count)(solution);
191
192        if n_entities == 0 || n_elements == 0 {
193            let _score = phase_scope.score_director_mut().calculate_score();
194            phase_scope.update_best_solution();
195            return;
196        }
197
198        let assigned: Vec<V> = (self.get_assigned)(phase_scope.score_director().working_solution());
199        if assigned.len() >= n_elements {
200            let _score = phase_scope.score_director_mut().calculate_score();
201            phase_scope.update_best_solution();
202            return;
203        }
204
205        let assigned_set: std::collections::HashSet<V> = assigned.into_iter().collect();
206        let mut entity_idx = 0;
207
208        for elem_idx in 0..n_elements {
209            if phase_scope.solver_scope().should_terminate_construction() {
210                break;
211            }
212
213            let element =
214                (self.index_to_element)(phase_scope.score_director().working_solution(), elem_idx);
215            if assigned_set.contains(&element) {
216                continue;
217            }
218
219            let mut step_scope = StepScope::new(&mut phase_scope);
220
221            {
222                let sd = step_scope.score_director_mut();
223                let insert_pos = (self.list_len)(sd.working_solution(), entity_idx);
224                sd.before_variable_changed(self.descriptor_index, entity_idx);
225                (self.list_insert)(sd.working_solution_mut(), entity_idx, insert_pos, element);
226                sd.after_variable_changed(self.descriptor_index, entity_idx);
227            }
228
229            let step_score = step_scope.calculate_score();
230            step_scope.set_step_score(step_score);
231            step_scope.complete();
232
233            entity_idx = (entity_idx + 1) % n_entities;
234        }
235
236        phase_scope.update_best_solution();
237    }
238
239    fn phase_type_name(&self) -> &'static str {
240        "ListRoundRobin"
241    }
242}
243
244// Builds the construction phase from config or defaults to cheapest insertion.
245#[allow(clippy::too_many_arguments)]
246pub fn build_list_construction<S, V>(
247    config: Option<&ConstructionHeuristicConfig>,
248    element_count: fn(&S) -> usize,
249    get_assigned: fn(&S) -> Vec<V>,
250    entity_count: fn(&S) -> usize,
251    list_len: fn(&S, usize) -> usize,
252    list_insert: fn(&mut S, usize, usize, V),
253    list_remove: fn(&mut S, usize, usize) -> V,
254    index_to_element: fn(&S, usize) -> V,
255    descriptor_index: usize,
256    depot_fn: Option<fn(&S) -> usize>,
257    distance_fn: Option<fn(&S, usize, usize) -> i64>,
258    element_load_fn: Option<fn(&S, usize) -> i64>,
259    capacity_fn: Option<fn(&S) -> i64>,
260    assign_route_fn: Option<fn(&mut S, usize, Vec<V>)>,
261    merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
262    k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
263    k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
264    k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
265    k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
266    k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
267) -> ListConstruction<S, V>
268where
269    S: PlanningSolution,
270    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + fmt::Debug + 'static,
271{
272    let Some((ch_type, k)) = config.map(|cfg| (cfg.construction_heuristic_type, cfg.k)) else {
273        return ListConstruction::CheapestInsertion(ListCheapestInsertionPhase::new(
274            element_count,
275            get_assigned,
276            entity_count,
277            list_len,
278            list_insert,
279            list_remove,
280            index_to_element,
281            descriptor_index,
282        ));
283    };
284
285    match ch_type {
286        ConstructionHeuristicType::ListRoundRobin => {
287            ListConstruction::RoundRobin(ListRoundRobinPhase {
288                element_count,
289                get_assigned,
290                entity_count,
291                list_len,
292                list_insert,
293                index_to_element,
294                descriptor_index,
295                _phantom: PhantomData,
296            })
297        }
298        ConstructionHeuristicType::ListRegretInsertion => {
299            ListConstruction::RegretInsertion(ListRegretInsertionPhase::new(
300                element_count,
301                get_assigned,
302                entity_count,
303                list_len,
304                list_insert,
305                list_remove,
306                index_to_element,
307                descriptor_index,
308            ))
309        }
310        ConstructionHeuristicType::ListClarkeWright => {
311            match (
312                depot_fn,
313                distance_fn,
314                element_load_fn,
315                capacity_fn,
316                assign_route_fn,
317            ) {
318                (Some(depot), Some(dist), Some(load), Some(cap), Some(assign)) => {
319                    ListConstruction::ClarkeWright(ListClarkeWrightPhase::new(
320                        element_count,
321                        get_assigned,
322                        entity_count,
323                        assign,
324                        index_to_element,
325                        depot,
326                        dist,
327                        load,
328                        cap,
329                        merge_feasible_fn,
330                        descriptor_index,
331                    ))
332                }
333                _ => {
334                    panic!(
335                        "list_clarke_wright requires depot_fn, distance_fn, \
336                         element_load_fn, capacity_fn, and assign_route_fn"
337                    );
338                }
339            }
340        }
341        ConstructionHeuristicType::ListKOpt => {
342            match (
343                k_opt_get_route,
344                k_opt_set_route,
345                k_opt_depot_fn,
346                k_opt_distance_fn,
347            ) {
348                (Some(get_route), Some(set_route), Some(ko_depot), Some(ko_dist)) => {
349                    ListConstruction::KOpt(ListKOptPhase::new(
350                        k,
351                        entity_count,
352                        get_route,
353                        set_route,
354                        ko_depot,
355                        ko_dist,
356                        k_opt_feasible_fn,
357                        descriptor_index,
358                    ))
359                }
360                _ => {
361                    panic!(
362                        "list_k_opt requires k_opt_get_route, k_opt_set_route, \
363                         k_opt_depot_fn, and k_opt_distance_fn"
364                    );
365                }
366            }
367        }
368        ConstructionHeuristicType::ListCheapestInsertion => {
369            ListConstruction::CheapestInsertion(ListCheapestInsertionPhase::new(
370                element_count,
371                get_assigned,
372                entity_count,
373                list_len,
374                list_insert,
375                list_remove,
376                index_to_element,
377                descriptor_index,
378            ))
379        }
380        ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
381            panic!(
382                "generic construction heuristic {:?} must be normalized before list construction",
383                ch_type
384            );
385        }
386        ConstructionHeuristicType::FirstFitDecreasing
387        | ConstructionHeuristicType::WeakestFit
388        | ConstructionHeuristicType::WeakestFitDecreasing
389        | ConstructionHeuristicType::StrongestFit
390        | ConstructionHeuristicType::StrongestFitDecreasing
391        | ConstructionHeuristicType::AllocateEntityFromQueue
392        | ConstructionHeuristicType::AllocateToValueFromQueue => {
393            panic!(
394                "standard construction heuristic {:?} configured against a list variable",
395                ch_type
396            );
397        }
398    }
399}
400
401#[cfg(test)]
402mod tests {
403    use super::*;
404    use solverforge_config::VariableTargetConfig;
405    use solverforge_core::score::SoftScore;
406
407    #[derive(Clone, Debug)]
408    struct TestSolution {
409        score: Option<SoftScore>,
410    }
411
412    impl PlanningSolution for TestSolution {
413        type Score = SoftScore;
414
415        fn score(&self) -> Option<Self::Score> {
416            self.score
417        }
418
419        fn set_score(&mut self, score: Option<Self::Score>) {
420            self.score = score;
421        }
422    }
423
424    fn config(kind: ConstructionHeuristicType) -> ConstructionHeuristicConfig {
425        ConstructionHeuristicConfig {
426            construction_heuristic_type: kind,
427            target: VariableTargetConfig::default(),
428            k: 2,
429            termination: None,
430        }
431    }
432
433    #[test]
434    fn list_builder_rejects_unnormalized_generic_construction() {
435        let panic = std::panic::catch_unwind(|| {
436            let _ = build_list_construction::<TestSolution, usize>(
437                Some(&config(ConstructionHeuristicType::FirstFit)),
438                |_| 0,
439                |_| Vec::new(),
440                |_| 0,
441                |_, _| 0,
442                |_, _, _, _| {},
443                |_, _, _| 0,
444                |_, _| 0,
445                0,
446                None,
447                None,
448                None,
449                None,
450                None,
451                None,
452                None,
453                None,
454                None,
455                None,
456                None,
457            );
458        })
459        .expect_err("unnormalized generic construction should panic");
460
461        let message = panic
462            .downcast_ref::<String>()
463            .map(String::as_str)
464            .or_else(|| panic.downcast_ref::<&'static str>().copied())
465            .unwrap_or("");
466        assert!(message.contains("must be normalized before list construction"));
467    }
468}
solverforge_solver/list_solver.rs

solverforge_solver/
list_solver.rs
