u_nesting_core/
solver.rs

1//! Solver traits and configuration.
2
3use crate::geometry::{Boundary, Geometry};
4use crate::result::SolveResult;
5use crate::Result;
6
7#[cfg(feature = "serde")]
8use serde::{Deserialize, Serialize};
9
10/// Optimization strategy.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
12#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
13pub enum Strategy {
14    /// Bottom-Left Fill (fast, lower quality).
15    #[default]
16    BottomLeftFill,
17    /// NFP-guided placement (balanced).
18    NfpGuided,
19    /// Genetic Algorithm (slower, higher quality).
20    GeneticAlgorithm,
21    /// Biased Random-Key Genetic Algorithm (balanced, robust).
22    Brkga,
23    /// Simulated Annealing.
24    SimulatedAnnealing,
25    /// Extreme Point heuristic (3D only).
26    ExtremePoint,
27    /// Goal-Driven Ruin and Recreate (GDRR).
28    Gdrr,
29    /// Adaptive Large Neighborhood Search (ALNS).
30    Alns,
31    /// MILP-based exact solver (small instances, optimal solution).
32    MilpExact,
33    /// Hybrid: Try exact first, fallback to heuristic on timeout.
34    HybridExact,
35}
36
37impl Strategy {
38    /// Parses a strategy name (case-insensitive, whitespace-trimmed).
39    ///
40    /// Returns `None` for unrecognized names so callers surface an explicit
41    /// error instead of silently falling back to a default strategy (which
42    /// hides typos from consumers). This is the single source of truth for
43    /// strategy-name parsing across all bindings (C FFI, Python, WASM).
44    /// The names [`Strategy::parse`] reads, one per strategy.
45    pub const NAMES: [&'static str; 10] = [
46        "blf",
47        "nfp",
48        "ga",
49        "brkga",
50        "sa",
51        "ep",
52        "gdrr",
53        "alns",
54        "milpexact",
55        "hybridexact",
56    ];
57
58    pub fn parse(name: &str) -> Option<Self> {
59        match name.trim().to_lowercase().as_str() {
60            "blf" | "bottomleftfill" => Some(Self::BottomLeftFill),
61            "nfp" | "nfpguided" => Some(Self::NfpGuided),
62            "ga" | "genetic" | "geneticalgorithm" => Some(Self::GeneticAlgorithm),
63            "brkga" => Some(Self::Brkga),
64            "sa" | "simulatedannealing" => Some(Self::SimulatedAnnealing),
65            "ep" | "extremepoint" => Some(Self::ExtremePoint),
66            "gdrr" => Some(Self::Gdrr),
67            "alns" => Some(Self::Alns),
68            "milpexact" | "exact" => Some(Self::MilpExact),
69            "hybridexact" | "hybrid" => Some(Self::HybridExact),
70            _ => None,
71        }
72    }
73}
74
75/// Common configuration for solvers.
76#[derive(Debug, Clone)]
77#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
78pub struct Config {
79    /// Optimization strategy.
80    pub strategy: Strategy,
81
82    /// Minimum distance between any two placed geometries. It does not apply
83    /// between a geometry and the boundary — that is `margin`.
84    pub spacing: f64,
85
86    /// Minimum distance between any placed geometry and the boundary edge.
87    pub margin: f64,
88
89    /// Maximum computation time in milliseconds (0 = unlimited).
90    ///
91    /// The search strategies check it between individual placements, so a solve
92    /// returns within the limit plus the time of the greedy bottom-left pass it is
93    /// compared against. The layout returned is the best one found in that time.
94    pub time_limit_ms: u64,
95
96    /// Target utilization (0.0 - 1.0). Solver stops if reached.
97    pub target_utilization: Option<f64>,
98
99    /// Number of threads to use (0 = auto).
100    pub threads: usize,
101
102    // GA-specific parameters
103    /// Population size for GA.
104    pub population_size: usize,
105
106    /// Number of generations for GA.
107    pub max_generations: u32,
108
109    /// Crossover rate for GA (0.0 - 1.0).
110    pub crossover_rate: f64,
111
112    /// Mutation rate for GA (0.0 - 1.0).
113    pub mutation_rate: f64,
114
115    /// Elite count for GA.
116    pub elite_count: usize,
117
118    /// Optional RNG seed for reproducible runs of the stochastic strategies
119    /// (GA, BRKGA, SA). `None` seeds from system entropy (non-deterministic).
120    pub seed: Option<u64>,
121}
122
123impl Default for Config {
124    fn default() -> Self {
125        Self {
126            strategy: Strategy::default(),
127            spacing: 0.0,
128            margin: 0.0,
129            time_limit_ms: 30000,
130            target_utilization: None,
131            threads: 0,
132            population_size: 100,
133            max_generations: 500,
134            crossover_rate: 0.85,
135            mutation_rate: 0.05,
136            elite_count: 5,
137            seed: None,
138        }
139    }
140}
141
142impl Config {
143    /// Creates a new configuration with default values.
144    pub fn new() -> Self {
145        Self::default()
146    }
147
148    /// Checks the fields a caller sets against their ranges -- the builders
149    /// store what they are given, and every solver calls this before it runs.
150    ///
151    /// # Errors
152    /// `ConfigError` naming the first field out of range: `spacing` or
153    /// `margin` negative or not finite, `crossover_rate`/`mutation_rate` or
154    /// `target_utilization` outside `[0, 1]`.
155    pub fn validate(&self) -> Result<()> {
156        use crate::error::{check_at_least, check_range};
157        check_at_least("spacing", self.spacing, 0.0)?;
158        check_at_least("margin", self.margin, 0.0)?;
159        check_range("crossover_rate", self.crossover_rate, 0.0, 1.0)?;
160        check_range("mutation_rate", self.mutation_rate, 0.0, 1.0)?;
161        if let Some(util) = self.target_utilization {
162            check_range("target_utilization", util, 0.0, 1.0)?;
163        }
164        Ok(())
165    }
166
167    /// Sets the optimization strategy.
168    pub fn with_strategy(mut self, strategy: Strategy) -> Self {
169        self.strategy = strategy;
170        self
171    }
172
173    /// Sets the spacing between geometries.
174    pub fn with_spacing(mut self, spacing: f64) -> Self {
175        self.spacing = spacing;
176        self
177    }
178
179    /// Sets the margin from boundary edges.
180    pub fn with_margin(mut self, margin: f64) -> Self {
181        self.margin = margin;
182        self
183    }
184
185    /// Sets the time limit in milliseconds.
186    pub fn with_time_limit(mut self, ms: u64) -> Self {
187        self.time_limit_ms = ms;
188        self
189    }
190
191    /// Sets the target utilization.
192    pub fn with_target_utilization(mut self, util: f64) -> Self {
193        self.target_utilization = Some(util);
194        self
195    }
196
197    /// Sets the RNG seed for reproducible stochastic runs (GA, BRKGA, SA).
198    pub fn with_seed(mut self, seed: u64) -> Self {
199        self.seed = Some(seed);
200        self
201    }
202}
203
204/// Progress callback for long-running operations.
205pub type ProgressCallback = Box<dyn Fn(ProgressInfo) + Send + Sync>;
206
207/// Progress information during solving.
208#[derive(Debug, Clone, Default)]
209pub struct ProgressInfo {
210    /// Current iteration/generation number.
211    pub iteration: u32,
212    /// Total expected iterations (0 if unknown).
213    pub total_iterations: u32,
214    /// Current best utilization (0.0 to 1.0).
215    pub utilization: f64,
216    /// Current best fitness value.
217    pub best_fitness: f64,
218    /// Number of items placed.
219    pub items_placed: usize,
220    /// Total number of items.
221    pub total_items: usize,
222    /// Elapsed time in milliseconds.
223    pub elapsed_ms: u64,
224    /// Current phase/stage description.
225    pub phase: String,
226    /// Whether the solver is still running.
227    pub running: bool,
228}
229
230impl ProgressInfo {
231    /// Creates a new progress info with default values.
232    pub fn new() -> Self {
233        Self {
234            running: true,
235            ..Default::default()
236        }
237    }
238
239    /// Sets the iteration info.
240    pub fn with_iteration(mut self, current: u32, total: u32) -> Self {
241        self.iteration = current;
242        self.total_iterations = total;
243        self
244    }
245
246    /// Sets the utilization.
247    pub fn with_utilization(mut self, utilization: f64) -> Self {
248        self.utilization = utilization;
249        self
250    }
251
252    /// Sets the best fitness.
253    pub fn with_fitness(mut self, fitness: f64) -> Self {
254        self.best_fitness = fitness;
255        self
256    }
257
258    /// Sets the items placed info.
259    pub fn with_items(mut self, placed: usize, total: usize) -> Self {
260        self.items_placed = placed;
261        self.total_items = total;
262        self
263    }
264
265    /// Sets the elapsed time.
266    pub fn with_elapsed(mut self, elapsed_ms: u64) -> Self {
267        self.elapsed_ms = elapsed_ms;
268        self
269    }
270
271    /// Sets the phase description.
272    pub fn with_phase(mut self, phase: impl Into<String>) -> Self {
273        self.phase = phase.into();
274        self
275    }
276
277    /// Marks the solver as finished.
278    pub fn finished(mut self) -> Self {
279        self.running = false;
280        self
281    }
282
283    /// Calculates the progress percentage (0.0 to 1.0).
284    pub fn progress_percent(&self) -> f64 {
285        if self.total_iterations > 0 {
286            self.iteration as f64 / self.total_iterations as f64
287        } else {
288            0.0
289        }
290    }
291}
292
293/// Trait for nesting/packing solvers.
294pub trait Solver {
295    /// The geometry type this solver handles.
296    type Geometry: Geometry;
297    /// The boundary type this solver handles.
298    type Boundary: Boundary;
299    /// The scalar type for coordinates.
300    type Scalar;
301
302    /// Solves the nesting/packing problem.
303    fn solve(
304        &self,
305        geometries: &[Self::Geometry],
306        boundary: &Self::Boundary,
307    ) -> Result<SolveResult<Self::Scalar>>;
308
309    /// Solves with a progress callback.
310    fn solve_with_progress(
311        &self,
312        geometries: &[Self::Geometry],
313        boundary: &Self::Boundary,
314        callback: ProgressCallback,
315    ) -> Result<SolveResult<Self::Scalar>>;
316
317    /// Cancels an ongoing solve operation.
318    fn cancel(&self);
319}
320
321#[cfg(test)]
322mod config_tests {
323    use super::Config;
324
325    #[test]
326    fn a_target_utilization_above_one_is_refused_not_clamped() {
327        let config = Config::default().with_target_utilization(1.5);
328        assert_eq!(config.target_utilization, Some(1.5), "stored as given");
329        let err = config.validate().expect_err("1.5 is not a utilization");
330        assert!(err.to_string().contains("target_utilization"), "{err}");
331        assert!(Config::default()
332            .with_target_utilization(0.9)
333            .validate()
334            .is_ok());
335        let nan_rate = Config {
336            mutation_rate: f64::NAN,
337            ..Config::default()
338        };
339        assert!(nan_rate.validate().is_err());
340    }
341}
u_nesting_core/solver.rs

u_nesting_core/
solver.rs
