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    /// Sets the optimization strategy.
135    pub fn with_strategy(mut self, strategy: Strategy) -> Self {
136        self.strategy = strategy;
137        self
138    }
139
140    /// Sets the spacing between geometries.
141    pub fn with_spacing(mut self, spacing: f64) -> Self {
142        self.spacing = spacing;
143        self
144    }
145
146    /// Sets the margin from boundary edges.
147    pub fn with_margin(mut self, margin: f64) -> Self {
148        self.margin = margin;
149        self
150    }
151
152    /// Sets the time limit in milliseconds.
153    pub fn with_time_limit(mut self, ms: u64) -> Self {
154        self.time_limit_ms = ms;
155        self
156    }
157
158    /// Sets the target utilization.
159    pub fn with_target_utilization(mut self, util: f64) -> Self {
160        self.target_utilization = Some(util.clamp(0.0, 1.0));
161        self
162    }
163
164    /// Sets the RNG seed for reproducible stochastic runs (GA, BRKGA, SA).
165    pub fn with_seed(mut self, seed: u64) -> Self {
166        self.seed = Some(seed);
167        self
168    }
169}
170
171/// Progress callback for long-running operations.
172pub type ProgressCallback = Box<dyn Fn(ProgressInfo) + Send + Sync>;
173
174/// Progress information during solving.
175#[derive(Debug, Clone, Default)]
176pub struct ProgressInfo {
177    /// Current iteration/generation number.
178    pub iteration: u32,
179    /// Total expected iterations (0 if unknown).
180    pub total_iterations: u32,
181    /// Current best utilization (0.0 to 1.0).
182    pub utilization: f64,
183    /// Current best fitness value.
184    pub best_fitness: f64,
185    /// Number of items placed.
186    pub items_placed: usize,
187    /// Total number of items.
188    pub total_items: usize,
189    /// Elapsed time in milliseconds.
190    pub elapsed_ms: u64,
191    /// Current phase/stage description.
192    pub phase: String,
193    /// Whether the solver is still running.
194    pub running: bool,
195}
196
197impl ProgressInfo {
198    /// Creates a new progress info with default values.
199    pub fn new() -> Self {
200        Self {
201            running: true,
202            ..Default::default()
203        }
204    }
205
206    /// Sets the iteration info.
207    pub fn with_iteration(mut self, current: u32, total: u32) -> Self {
208        self.iteration = current;
209        self.total_iterations = total;
210        self
211    }
212
213    /// Sets the utilization.
214    pub fn with_utilization(mut self, utilization: f64) -> Self {
215        self.utilization = utilization;
216        self
217    }
218
219    /// Sets the best fitness.
220    pub fn with_fitness(mut self, fitness: f64) -> Self {
221        self.best_fitness = fitness;
222        self
223    }
224
225    /// Sets the items placed info.
226    pub fn with_items(mut self, placed: usize, total: usize) -> Self {
227        self.items_placed = placed;
228        self.total_items = total;
229        self
230    }
231
232    /// Sets the elapsed time.
233    pub fn with_elapsed(mut self, elapsed_ms: u64) -> Self {
234        self.elapsed_ms = elapsed_ms;
235        self
236    }
237
238    /// Sets the phase description.
239    pub fn with_phase(mut self, phase: impl Into<String>) -> Self {
240        self.phase = phase.into();
241        self
242    }
243
244    /// Marks the solver as finished.
245    pub fn finished(mut self) -> Self {
246        self.running = false;
247        self
248    }
249
250    /// Calculates the progress percentage (0.0 to 1.0).
251    pub fn progress_percent(&self) -> f64 {
252        if self.total_iterations > 0 {
253            self.iteration as f64 / self.total_iterations as f64
254        } else {
255            0.0
256        }
257    }
258}
259
260/// Trait for nesting/packing solvers.
261pub trait Solver {
262    /// The geometry type this solver handles.
263    type Geometry: Geometry;
264    /// The boundary type this solver handles.
265    type Boundary: Boundary;
266    /// The scalar type for coordinates.
267    type Scalar;
268
269    /// Solves the nesting/packing problem.
270    fn solve(
271        &self,
272        geometries: &[Self::Geometry],
273        boundary: &Self::Boundary,
274    ) -> Result<SolveResult<Self::Scalar>>;
275
276    /// Solves with a progress callback.
277    fn solve_with_progress(
278        &self,
279        geometries: &[Self::Geometry],
280        boundary: &Self::Boundary,
281        callback: ProgressCallback,
282    ) -> Result<SolveResult<Self::Scalar>>;
283
284    /// Cancels an ongoing solve operation.
285    fn cancel(&self);
286}
u_nesting_core/solver.rs

u_nesting_core/
solver.rs
