solverforge_solver/phase/partitioned/
partitioner.rs

1/* Solution partitioner for dividing problems into independent sub-problems.
2
3Partitioners split a large problem into smaller pieces that can be
4solved independently (potentially in parallel), then merged back together.
5*/
6
7use std::fmt::Debug;
8
9use solverforge_core::domain::PlanningSolution;
10
11/// Splits a solution into independent partitions for parallel solving.
12///
13/// Each partition should be solvable independently without affecting
14/// the correctness of other partitions. The partitioner must also be
15/// able to merge the solved partitions back into a complete solution.
16///
17/// # Type Parameters
18///
19/// - `S`: The planning solution type
20///
21/// # Example
22///
23/// For a school timetabling problem, a natural partitioning might be
24/// by room or by time period, where each partition contains lessons
25/// that don't interact with lessons in other partitions.
26pub trait SolutionPartitioner<S: PlanningSolution>: Send + Sync + Debug {
27    /* Splits the solution into independent partitions.
28
29    Each returned solution should be a subset of the original that
30    can be optimized independently. The union of all partitions should
31    cover all entities in the original solution.
32
33    # Arguments
34
35    * `solution` - The solution to partition
36
37    # Returns
38
39    A vector of partial solutions, one per partition.
40    */
41    fn partition(&self, solution: &S) -> Vec<S>;
42
43    /* Merges solved partitions back into a complete solution.
44
45    This is called after all partitions have been solved to combine
46    them into the final result.
47
48    # Arguments
49
50    * `original` - The original unpartitioned solution
51    * `partitions` - The solved partition solutions
52
53    # Returns
54
55    The merged complete solution.
56    */
57    fn merge(&self, original: &S, partitions: Vec<S>) -> S;
58
59    /* Returns the recommended number of partitions.
60
61    This can be used by the partitioned search phase to determine
62    how many threads to use. Returns `None` if no recommendation.
63    */
64    fn recommended_partition_count(&self) -> Option<usize> {
65        None
66    }
67}
68
69/// A simple partitioner that creates a specified number of partitions.
70///
71/// This is a reference implementation that can be customized via
72/// closures for the actual partitioning and merging logic.
73pub struct FunctionalPartitioner<S, PF, MF>
74where
75    S: PlanningSolution,
76    PF: Fn(&S) -> Vec<S> + Send + Sync,
77    MF: Fn(&S, Vec<S>) -> S + Send + Sync,
78{
79    partition_fn: PF,
80    merge_fn: MF,
81    recommended_count: Option<usize>,
82    _phantom: std::marker::PhantomData<fn() -> S>,
83}
84
85impl<S, PF, MF> FunctionalPartitioner<S, PF, MF>
86where
87    S: PlanningSolution,
88    PF: Fn(&S) -> Vec<S> + Send + Sync,
89    MF: Fn(&S, Vec<S>) -> S + Send + Sync,
90{
91    pub fn new(partition_fn: PF, merge_fn: MF) -> Self {
92        Self {
93            partition_fn,
94            merge_fn,
95            recommended_count: None,
96            _phantom: std::marker::PhantomData,
97        }
98    }
99
100    pub fn with_recommended_count(mut self, count: usize) -> Self {
101        self.recommended_count = Some(count);
102        self
103    }
104}
105
106impl<S, PF, MF> Debug for FunctionalPartitioner<S, PF, MF>
107where
108    S: PlanningSolution,
109    PF: Fn(&S) -> Vec<S> + Send + Sync,
110    MF: Fn(&S, Vec<S>) -> S + Send + Sync,
111{
112    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
113        f.debug_struct("FunctionalPartitioner")
114            .field("recommended_count", &self.recommended_count)
115            .finish()
116    }
117}
118
119impl<S, PF, MF> SolutionPartitioner<S> for FunctionalPartitioner<S, PF, MF>
120where
121    S: PlanningSolution,
122    PF: Fn(&S) -> Vec<S> + Send + Sync,
123    MF: Fn(&S, Vec<S>) -> S + Send + Sync,
124{
125    fn partition(&self, solution: &S) -> Vec<S> {
126        (self.partition_fn)(solution)
127    }
128
129    fn merge(&self, original: &S, partitions: Vec<S>) -> S {
130        (self.merge_fn)(original, partitions)
131    }
132
133    fn recommended_partition_count(&self) -> Option<usize> {
134        self.recommended_count
135    }
136}
137
138// Thread count configuration for partitioned search.
139#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
140pub enum ThreadCount {
141    // Automatically determine based on available CPU cores.
142    #[default]
143    Auto,
144    // Use all available CPU cores.
145    Unlimited,
146    // Use a specific number of threads.
147    Specific(usize),
148}
149
150impl ThreadCount {
151    /// Resolves the thread count to an actual number.
152    ///
153    /// # Arguments
154    ///
155    /// * `partition_count` - Number of partitions to process
156    ///
157    /// # Returns
158    ///
159    /// The number of threads to use.
160    pub fn resolve(&self, partition_count: usize) -> usize {
161        match self {
162            ThreadCount::Auto => {
163                let cpus = std::thread::available_parallelism()
164                    .map(|p| p.get())
165                    .unwrap_or(1);
166                std::cmp::min(cpus, partition_count)
167            }
168            ThreadCount::Unlimited => std::thread::available_parallelism()
169                .map(|p| p.get())
170                .unwrap_or(1),
171            ThreadCount::Specific(n) => std::cmp::min(*n, partition_count),
172        }
173    }
174}
175
176impl std::fmt::Display for ThreadCount {
177    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
178        match self {
179            ThreadCount::Auto => write!(f, "Auto"),
180            ThreadCount::Unlimited => write!(f, "Unlimited"),
181            ThreadCount::Specific(n) => write!(f, "{}", n),
182        }
183    }
184}
185
186#[cfg(test)]
187#[path = "partitioner_tests.rs"]
188mod tests;
solverforge_solver/phase/partitioned/partitioner.rs

solverforge_solver/phase/partitioned/
partitioner.rs
