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

u_nesting_core/
solver.rs
