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
210                .solver_scope_mut()
211                .should_terminate_construction()
212            {
213                break;
214            }
215
216            let element =
217                (self.index_to_element)(phase_scope.score_director().working_solution(), elem_idx);
218            if assigned_set.contains(&element) {
219                continue;
220            }
221
222            let mut step_scope = StepScope::new(&mut phase_scope);
223
224            {
225                let sd = step_scope.score_director_mut();
226                let insert_pos = (self.list_len)(sd.working_solution(), entity_idx);
227                sd.before_variable_changed(self.descriptor_index, entity_idx);
228                (self.list_insert)(sd.working_solution_mut(), entity_idx, insert_pos, element);
229                sd.after_variable_changed(self.descriptor_index, entity_idx);
230            }
231
232            let step_score = step_scope.calculate_score();
233            step_scope.set_step_score(step_score);
234            step_scope.complete();
235
236            entity_idx = (entity_idx + 1) % n_entities;
237        }
238
239        phase_scope.update_best_solution();
240    }
241
242    fn phase_type_name(&self) -> &'static str {
243        "ListRoundRobin"
244    }
245}
246
247// Builds the construction phase from config or defaults to cheapest insertion.
248#[allow(clippy::too_many_arguments)]
249pub fn build_list_construction<S, V>(
250    config: Option<&ConstructionHeuristicConfig>,
251    element_count: fn(&S) -> usize,
252    get_assigned: fn(&S) -> Vec<V>,
253    entity_count: fn(&S) -> usize,
254    list_len: fn(&S, usize) -> usize,
255    list_insert: fn(&mut S, usize, usize, V),
256    list_remove: fn(&mut S, usize, usize) -> V,
257    index_to_element: fn(&S, usize) -> V,
258    descriptor_index: usize,
259    depot_fn: Option<fn(&S) -> usize>,
260    distance_fn: Option<fn(&S, usize, usize) -> i64>,
261    element_load_fn: Option<fn(&S, usize) -> i64>,
262    capacity_fn: Option<fn(&S) -> i64>,
263    assign_route_fn: Option<fn(&mut S, usize, Vec<V>)>,
264    merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
265    k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
266    k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
267    k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
268    k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
269    k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
270) -> ListConstruction<S, V>
271where
272    S: PlanningSolution,
273    V: Copy + PartialEq + Eq + std::hash::Hash + Send + Sync + fmt::Debug + 'static,
274{
275    let Some((ch_type, k)) = config.map(|cfg| (cfg.construction_heuristic_type, cfg.k)) else {
276        return ListConstruction::CheapestInsertion(ListCheapestInsertionPhase::new(
277            element_count,
278            get_assigned,
279            entity_count,
280            list_len,
281            list_insert,
282            list_remove,
283            index_to_element,
284            descriptor_index,
285        ));
286    };
287
288    match ch_type {
289        ConstructionHeuristicType::ListRoundRobin => {
290            ListConstruction::RoundRobin(ListRoundRobinPhase {
291                element_count,
292                get_assigned,
293                entity_count,
294                list_len,
295                list_insert,
296                index_to_element,
297                descriptor_index,
298                _phantom: PhantomData,
299            })
300        }
301        ConstructionHeuristicType::ListRegretInsertion => {
302            ListConstruction::RegretInsertion(ListRegretInsertionPhase::new(
303                element_count,
304                get_assigned,
305                entity_count,
306                list_len,
307                list_insert,
308                list_remove,
309                index_to_element,
310                descriptor_index,
311            ))
312        }
313        ConstructionHeuristicType::ListClarkeWright => {
314            match (
315                depot_fn,
316                distance_fn,
317                element_load_fn,
318                capacity_fn,
319                assign_route_fn,
320            ) {
321                (Some(depot), Some(dist), Some(load), Some(cap), Some(assign)) => {
322                    ListConstruction::ClarkeWright(ListClarkeWrightPhase::new(
323                        element_count,
324                        get_assigned,
325                        entity_count,
326                        assign,
327                        index_to_element,
328                        depot,
329                        dist,
330                        load,
331                        cap,
332                        merge_feasible_fn,
333                        descriptor_index,
334                    ))
335                }
336                _ => {
337                    panic!(
338                        "list_clarke_wright requires depot_fn, distance_fn, \
339                         element_load_fn, capacity_fn, and assign_route_fn"
340                    );
341                }
342            }
343        }
344        ConstructionHeuristicType::ListKOpt => {
345            match (
346                k_opt_get_route,
347                k_opt_set_route,
348                k_opt_depot_fn,
349                k_opt_distance_fn,
350            ) {
351                (Some(get_route), Some(set_route), Some(ko_depot), Some(ko_dist)) => {
352                    ListConstruction::KOpt(ListKOptPhase::new(
353                        k,
354                        entity_count,
355                        get_route,
356                        set_route,
357                        ko_depot,
358                        ko_dist,
359                        k_opt_feasible_fn,
360                        descriptor_index,
361                    ))
362                }
363                _ => {
364                    panic!(
365                        "list_k_opt requires k_opt_get_route, k_opt_set_route, \
366                         k_opt_depot_fn, and k_opt_distance_fn"
367                    );
368                }
369            }
370        }
371        ConstructionHeuristicType::ListCheapestInsertion => {
372            ListConstruction::CheapestInsertion(ListCheapestInsertionPhase::new(
373                element_count,
374                get_assigned,
375                entity_count,
376                list_len,
377                list_insert,
378                list_remove,
379                index_to_element,
380                descriptor_index,
381            ))
382        }
383        ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
384            panic!(
385                "generic construction heuristic {:?} must be normalized before list construction",
386                ch_type
387            );
388        }
389        ConstructionHeuristicType::FirstFitDecreasing
390        | ConstructionHeuristicType::WeakestFit
391        | ConstructionHeuristicType::WeakestFitDecreasing
392        | ConstructionHeuristicType::StrongestFit
393        | ConstructionHeuristicType::StrongestFitDecreasing
394        | ConstructionHeuristicType::AllocateEntityFromQueue
395        | ConstructionHeuristicType::AllocateToValueFromQueue => {
396            panic!(
397                "standard construction heuristic {:?} configured against a list variable",
398                ch_type
399            );
400        }
401    }
402}
403
404#[cfg(test)]
405mod tests {
406    use super::*;
407    use solverforge_config::VariableTargetConfig;
408    use solverforge_core::score::SoftScore;
409
410    #[derive(Clone, Debug)]
411    struct TestSolution {
412        score: Option<SoftScore>,
413    }
414
415    impl PlanningSolution for TestSolution {
416        type Score = SoftScore;
417
418        fn score(&self) -> Option<Self::Score> {
419            self.score
420        }
421
422        fn set_score(&mut self, score: Option<Self::Score>) {
423            self.score = score;
424        }
425    }
426
427    fn config(kind: ConstructionHeuristicType) -> ConstructionHeuristicConfig {
428        ConstructionHeuristicConfig {
429            construction_heuristic_type: kind,
430            target: VariableTargetConfig::default(),
431            k: 2,
432            termination: None,
433        }
434    }
435
436    #[test]
437    fn list_builder_rejects_unnormalized_generic_construction() {
438        let panic = std::panic::catch_unwind(|| {
439            let _ = build_list_construction::<TestSolution, usize>(
440                Some(&config(ConstructionHeuristicType::FirstFit)),
441                |_| 0,
442                |_| Vec::new(),
443                |_| 0,
444                |_, _| 0,
445                |_, _, _, _| {},
446                |_, _, _| 0,
447                |_, _| 0,
448                0,
449                None,
450                None,
451                None,
452                None,
453                None,
454                None,
455                None,
456                None,
457                None,
458                None,
459                None,
460            );
461        })
462        .expect_err("unnormalized generic construction should panic");
463
464        let message = panic
465            .downcast_ref::<String>()
466            .map(String::as_str)
467            .or_else(|| panic.downcast_ref::<&'static str>().copied())
468            .unwrap_or("");
469        assert!(message.contains("must be normalized before list construction"));
470    }
471}
solverforge_solver/list_solver.rs

solverforge_solver/
list_solver.rs
