solverforge_solver/phase/partitioned/
phase.rs

1// PartitionedSearchPhase implementation.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use rayon::prelude::*;
7use rayon::ThreadPoolBuilder;
8use solverforge_core::domain::PlanningSolution;
9use solverforge_scoring::Director;
10
11use crate::phase::Phase;
12use crate::scope::ProgressCallback;
13use crate::scope::SolverScope;
14
15use super::child_phases::ChildPhases;
16use super::config::PartitionedSearchConfig;
17use super::partitioner::SolutionPartitioner;
18
19/// Partitioned search phase that solves partitions in parallel.
20///
21/// This phase:
22/// 1. Partitions the solution using the provided partitioner
23/// 2. Creates a solver for each partition
24/// 3. Runs child phases on each partition in parallel
25/// 4. Merges the solved partitions back together
26///
27/// Each partition runs independently with its own solver scope.
28///
29/// # Type Parameters
30///
31/// * `S` - The solution type
32/// * `D` - The main solver's score director type
33/// * `PD` - The score director type for partition solvers
34/// * `Part` - The partitioner type (implements `SolutionPartitioner<S>`)
35/// * `SDF` - The score director factory function type
36/// * `PF` - The phase factory function type
37/// * `CP` - The child phases type (tuple of phases)
38pub struct PartitionedSearchPhase<S, D, PD, Part, SDF, PF, CP>
39where
40    S: PlanningSolution,
41    D: Director<S>,
42    PD: Director<S>,
43    Part: SolutionPartitioner<S>,
44    SDF: Fn(S) -> PD + Send + Sync,
45    PF: Fn() -> CP + Send + Sync,
46    CP: ChildPhases<S, PD>,
47{
48    // The partitioner that splits and merges solutions.
49    partitioner: Part,
50
51    // Factory for creating score directors for each partition.
52    score_director_factory: SDF,
53
54    // Factory for creating child phases for each partition.
55    phase_factory: PF,
56
57    // Configuration for this phase.
58    config: PartitionedSearchConfig,
59
60    _marker: PhantomData<fn(S, D, PD, CP)>,
61}
62
63impl<S, D, PD, Part, SDF, PF, CP> PartitionedSearchPhase<S, D, PD, Part, SDF, PF, CP>
64where
65    S: PlanningSolution,
66    D: Director<S>,
67    PD: Director<S>,
68    Part: SolutionPartitioner<S>,
69    SDF: Fn(S) -> PD + Send + Sync,
70    PF: Fn() -> CP + Send + Sync,
71    CP: ChildPhases<S, PD>,
72{
73    pub fn new(partitioner: Part, score_director_factory: SDF, phase_factory: PF) -> Self {
74        Self {
75            partitioner,
76            score_director_factory,
77            phase_factory,
78            config: PartitionedSearchConfig::default(),
79            _marker: PhantomData,
80        }
81    }
82
83    pub fn with_config(
84        partitioner: Part,
85        score_director_factory: SDF,
86        phase_factory: PF,
87        config: PartitionedSearchConfig,
88    ) -> Self {
89        Self {
90            partitioner,
91            score_director_factory,
92            phase_factory,
93            config,
94            _marker: PhantomData,
95        }
96    }
97}
98
99impl<S, D, PD, Part, SDF, PF, CP> Debug for PartitionedSearchPhase<S, D, PD, Part, SDF, PF, CP>
100where
101    S: PlanningSolution,
102    D: Director<S>,
103    PD: Director<S>,
104    Part: SolutionPartitioner<S> + Debug,
105    SDF: Fn(S) -> PD + Send + Sync,
106    PF: Fn() -> CP + Send + Sync,
107    CP: ChildPhases<S, PD>,
108{
109    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
110        f.debug_struct("PartitionedSearchPhase")
111            .field("partitioner", &self.partitioner)
112            .field("config", &self.config)
113            .finish()
114    }
115}
116
117impl<S, D, BestCb, PD, Part, SDF, PF, CP> Phase<S, D, BestCb>
118    for PartitionedSearchPhase<S, D, PD, Part, SDF, PF, CP>
119where
120    S: PlanningSolution + 'static,
121    D: Director<S>,
122    BestCb: ProgressCallback<S>,
123    PD: Director<S> + 'static,
124    Part: SolutionPartitioner<S>,
125    SDF: Fn(S) -> PD + Send + Sync,
126    PF: Fn() -> CP + Send + Sync,
127    CP: ChildPhases<S, PD> + Send,
128{
129    fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
130        // Get the current solution
131        let solution = solver_scope.score_director().working_solution().clone();
132
133        // Partition the solution
134        let partitions = self.partitioner.partition(&solution);
135        let partition_count = partitions.len();
136
137        if partition_count == 0 {
138            return;
139        }
140
141        // Determine thread count
142        let thread_count = self.config.thread_count.resolve(partition_count);
143
144        if self.config.log_progress {
145            tracing::info!(event = "phase_start", phase = "PartitionedSearch",);
146        }
147
148        let solved_partitions = self.solve_partitions(partitions, thread_count);
149
150        // Merge the solved partitions
151        let merged = self.partitioner.merge(&solution, solved_partitions);
152
153        // Update the working solution with the merged result
154        solver_scope.replace_working_solution_and_reinitialize(merged);
155
156        // Update best solution
157        solver_scope.update_best_solution();
158
159        if self.config.log_progress {
160            if let Some(score) = solver_scope.best_score() {
161                tracing::info!(
162                    event = "phase_end",
163                    phase = "PartitionedSearch",
164                    score = %format!("{:?}", score),
165                );
166            }
167        }
168    }
169
170    fn phase_type_name(&self) -> &'static str {
171        "PartitionedSearch"
172    }
173}
174
175impl<S, D, PD, Part, SDF, PF, CP> PartitionedSearchPhase<S, D, PD, Part, SDF, PF, CP>
176where
177    S: PlanningSolution,
178    D: Director<S>,
179    PD: Director<S>,
180    Part: SolutionPartitioner<S>,
181    SDF: Fn(S) -> PD + Send + Sync,
182    PF: Fn() -> CP + Send + Sync,
183    CP: ChildPhases<S, PD>,
184{
185    // Solves a single partition and returns the solved solution.
186    fn solve_partition(&self, partition: S) -> S {
187        // Create score director for this partition
188        let director = (self.score_director_factory)(partition);
189
190        // Create solver scope
191        let mut solver_scope = SolverScope::new(director);
192        solver_scope.initialize_working_solution_as_best();
193
194        // Create and run child phases
195        let mut phases = (self.phase_factory)();
196        phases.solve_all(&mut solver_scope);
197
198        // Return the best solution (or working solution if no best)
199        solver_scope.take_best_or_working_solution()
200    }
201
202    fn solve_partitions(&self, partitions: Vec<S>, thread_count: usize) -> Vec<S> {
203        if thread_count <= 1 || partitions.len() <= 1 {
204            return partitions
205                .into_iter()
206                .map(|partition| self.solve_partition(partition))
207                .collect();
208        }
209
210        ThreadPoolBuilder::new()
211            .num_threads(thread_count)
212            .build()
213            .expect("failed to build partitioned search rayon pool")
214            .install(|| {
215                partitions
216                    .into_par_iter()
217                    .map(|partition| self.solve_partition(partition))
218                    .collect()
219            })
220    }
221}
222
223#[cfg(test)]
224#[path = "phase_tests.rs"]
225mod tests;
solverforge_solver/phase/partitioned/phase.rs

solverforge_solver/phase/partitioned/
phase.rs
