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 /// The short name of each strategy -- what a refusal of an unknown name
39 /// lists as expected. [`Strategy::parse`] reads these and the longer
40 /// forms in [`Strategy::SPELLINGS`].
41 pub const NAMES: [&'static str; 10] = [
42 "blf",
43 "nfp",
44 "ga",
45 "brkga",
46 "sa",
47 "ep",
48 "gdrr",
49 "alns",
50 "milpexact",
51 "hybridexact",
52 ];
53
54 /// Every spelling [`Strategy::parse`] reads, with the strategy it names:
55 /// the [`Strategy::NAMES`] and their longer forms.
56 pub const SPELLINGS: [(&'static str, Self); 18] = [
57 ("blf", Self::BottomLeftFill),
58 ("bottomleftfill", Self::BottomLeftFill),
59 ("nfp", Self::NfpGuided),
60 ("nfpguided", Self::NfpGuided),
61 ("ga", Self::GeneticAlgorithm),
62 ("genetic", Self::GeneticAlgorithm),
63 ("geneticalgorithm", Self::GeneticAlgorithm),
64 ("brkga", Self::Brkga),
65 ("sa", Self::SimulatedAnnealing),
66 ("simulatedannealing", Self::SimulatedAnnealing),
67 ("ep", Self::ExtremePoint),
68 ("extremepoint", Self::ExtremePoint),
69 ("gdrr", Self::Gdrr),
70 ("alns", Self::Alns),
71 ("milpexact", Self::MilpExact),
72 ("exact", Self::MilpExact),
73 ("hybridexact", Self::HybridExact),
74 ("hybrid", Self::HybridExact),
75 ];
76
77 /// Parses a strategy name (case-insensitive, whitespace-trimmed).
78 ///
79 /// Returns `None` for unrecognized names so callers surface an explicit
80 /// error instead of silently falling back to a default strategy (which
81 /// hides typos from consumers). This is the single source of truth for
82 /// strategy-name parsing across all bindings (C FFI, Python, WASM).
83 pub fn parse(name: &str) -> Option<Self> {
84 let name = name.trim().to_lowercase();
85 Self::SPELLINGS
86 .iter()
87 .find(|(spelling, _)| *spelling == name)
88 .map(|&(_, strategy)| strategy)
89 }
90}
91
92/// Common configuration for solvers.
93#[derive(Debug, Clone)]
94#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
95pub struct Config {
96 /// Optimization strategy.
97 pub strategy: Strategy,
98
99 /// Minimum distance between any two placed geometries. It does not apply
100 /// between a geometry and the boundary — that is `margin`.
101 pub spacing: f64,
102
103 /// Minimum distance between any placed geometry and the boundary edge.
104 pub margin: f64,
105
106 /// Maximum computation time in milliseconds (0 = unlimited).
107 ///
108 /// The search strategies check it between individual placements, so a solve
109 /// returns within the limit plus the time of the greedy bottom-left pass it is
110 /// compared against. The layout returned is the best one found in that time.
111 pub time_limit_ms: u64,
112
113 /// Target utilization (0.0 - 1.0). Solver stops if reached.
114 pub target_utilization: Option<f64>,
115
116 /// Number of threads to use (0 = auto).
117 pub threads: usize,
118
119 // GA-specific parameters
120 /// Population size for the population-based strategies (GA, BRKGA).
121 ///
122 /// `None` runs each strategy with the size it is tuned for -- 2D GA and
123 /// BRKGA 30, 3D GA 100, 3D BRKGA 50; `Some(n)` runs it with `n`, at least
124 /// 2. The other strategies have no population and do not read it.
125 pub population_size: Option<usize>,
126
127 /// Generation budget for the population-based strategies (GA, BRKGA).
128 ///
129 /// `None` runs each strategy with the budget it is tuned for -- 2D GA and
130 /// BRKGA 50, 3D GA 500, 3D BRKGA 100; `Some(n)` allows `n` generations (0
131 /// evaluates the first population only). A run also ends on the time
132 /// limit, on cancellation and when the best layout stops improving.
133 pub max_generations: Option<u32>,
134
135 /// Crossover rate for GA (0.0 - 1.0).
136 pub crossover_rate: f64,
137
138 /// Mutation rate for GA (0.0 - 1.0).
139 pub mutation_rate: f64,
140
141 /// Elite count for GA.
142 pub elite_count: usize,
143
144 /// Optional RNG seed for reproducible runs of the stochastic strategies
145 /// (GA, BRKGA, SA, GDRR, ALNS -- 2D and 3D). `None` seeds from system
146 /// entropy (non-deterministic).
147 ///
148 /// A seeded run draws every random choice from the seed, so the same
149 /// request with the same seed returns the same layout **when the run ends
150 /// on its own budget** -- the generation or iteration count, convergence,
151 /// or the target utilization. A run cut short by the clock is not
152 /// reproduced: how far a search gets before `time_limit_ms` (or a
153 /// cancellation) stops it depends on the machine and its load. In 2D a
154 /// search keeps a time budget of its own even when `time_limit_ms` is 0
155 /// (15 s for GA and BRKGA, 10 s for SA, GDRR and ALNS), so a large 2D
156 /// request can reach it.
157 pub seed: Option<u64>,
158}
159
160impl Default for Config {
161 fn default() -> Self {
162 Self {
163 strategy: Strategy::default(),
164 spacing: 0.0,
165 margin: 0.0,
166 time_limit_ms: 30000,
167 target_utilization: None,
168 threads: 0,
169 population_size: None,
170 max_generations: None,
171 crossover_rate: 0.85,
172 mutation_rate: 0.05,
173 elite_count: 5,
174 seed: None,
175 }
176 }
177}
178
179impl Config {
180 /// Creates a new configuration with default values.
181 pub fn new() -> Self {
182 Self::default()
183 }
184
185 /// Checks the fields a caller sets against their ranges -- the builders
186 /// store what they are given, and every solver calls this before it runs.
187 ///
188 /// # Errors
189 /// `ConfigError` naming the first field out of range: `spacing` or
190 /// `margin` negative or not finite, `crossover_rate`/`mutation_rate` or
191 /// `target_utilization` outside `[0, 1]`, a `population_size` set below 2.
192 pub fn validate(&self) -> Result<()> {
193 use crate::error::{check_at_least, check_range};
194 check_at_least("spacing", self.spacing, 0.0)?;
195 check_at_least("margin", self.margin, 0.0)?;
196 if let Some(size) = self.population_size {
197 Self::check_population_size(size as i128)?;
198 }
199 check_range("crossover_rate", self.crossover_rate, 0.0, 1.0)?;
200 check_range("mutation_rate", self.mutation_rate, 0.0, 1.0)?;
201 if let Some(util) = self.target_utilization {
202 check_range("target_utilization", util, 0.0, 1.0)?;
203 }
204 Ok(())
205 }
206
207 /// A population size: at least 2, the fewest a generation can cross. A
208 /// request's value and a configuration's own are judged here alike.
209 pub(crate) fn check_population_size(value: i128) -> Result<usize> {
210 crate::error::whole_at_least("population_size", value, 2)
211 }
212
213 /// Sets the optimization strategy.
214 pub fn with_strategy(mut self, strategy: Strategy) -> Self {
215 self.strategy = strategy;
216 self
217 }
218
219 /// Sets the spacing between geometries.
220 pub fn with_spacing(mut self, spacing: f64) -> Self {
221 self.spacing = spacing;
222 self
223 }
224
225 /// Sets the margin from boundary edges.
226 pub fn with_margin(mut self, margin: f64) -> Self {
227 self.margin = margin;
228 self
229 }
230
231 /// Sets the time limit in milliseconds.
232 pub fn with_time_limit(mut self, ms: u64) -> Self {
233 self.time_limit_ms = ms;
234 self
235 }
236
237 /// Sets the target utilization.
238 pub fn with_target_utilization(mut self, util: f64) -> Self {
239 self.target_utilization = Some(util);
240 self
241 }
242
243 /// Sets the RNG seed for reproducible stochastic runs (see [`Config::seed`]).
244 pub fn with_seed(mut self, seed: u64) -> Self {
245 self.seed = Some(seed);
246 self
247 }
248
249 /// Sets the population size of the population-based strategies, in place
250 /// of each strategy's own (see [`Config::population_size`]).
251 pub fn with_population_size(mut self, size: usize) -> Self {
252 self.population_size = Some(size);
253 self
254 }
255
256 /// Sets the generation budget of the population-based strategies, in
257 /// place of each strategy's own (see [`Config::max_generations`]).
258 pub fn with_max_generations(mut self, generations: u32) -> Self {
259 self.max_generations = Some(generations);
260 self
261 }
262}
263
264/// Progress callback for long-running operations.
265pub type ProgressCallback = Box<dyn Fn(ProgressInfo) + Send + Sync>;
266
267/// Progress information during solving.
268#[derive(Debug, Clone, Default)]
269pub struct ProgressInfo {
270 /// Current iteration/generation number.
271 pub iteration: u32,
272 /// Total expected iterations (0 if unknown).
273 pub total_iterations: u32,
274 /// Current best utilization (0.0 to 1.0).
275 pub utilization: f64,
276 /// Current best fitness value.
277 pub best_fitness: f64,
278 /// Number of items placed.
279 pub items_placed: usize,
280 /// Total number of items.
281 pub total_items: usize,
282 /// Elapsed time in milliseconds.
283 pub elapsed_ms: u64,
284 /// Current phase/stage description.
285 pub phase: String,
286 /// Whether the solver is still running.
287 pub running: bool,
288}
289
290impl ProgressInfo {
291 /// Creates a new progress info with default values.
292 pub fn new() -> Self {
293 Self {
294 running: true,
295 ..Default::default()
296 }
297 }
298
299 /// Sets the iteration info.
300 pub fn with_iteration(mut self, current: u32, total: u32) -> Self {
301 self.iteration = current;
302 self.total_iterations = total;
303 self
304 }
305
306 /// Sets the utilization.
307 pub fn with_utilization(mut self, utilization: f64) -> Self {
308 self.utilization = utilization;
309 self
310 }
311
312 /// Sets the best fitness.
313 pub fn with_fitness(mut self, fitness: f64) -> Self {
314 self.best_fitness = fitness;
315 self
316 }
317
318 /// Sets the items placed info.
319 pub fn with_items(mut self, placed: usize, total: usize) -> Self {
320 self.items_placed = placed;
321 self.total_items = total;
322 self
323 }
324
325 /// Sets the elapsed time.
326 pub fn with_elapsed(mut self, elapsed_ms: u64) -> Self {
327 self.elapsed_ms = elapsed_ms;
328 self
329 }
330
331 /// Sets the phase description.
332 pub fn with_phase(mut self, phase: impl Into<String>) -> Self {
333 self.phase = phase.into();
334 self
335 }
336
337 /// Marks the solver as finished.
338 pub fn finished(mut self) -> Self {
339 self.running = false;
340 self
341 }
342
343 /// Calculates the progress percentage (0.0 to 1.0).
344 pub fn progress_percent(&self) -> f64 {
345 if self.total_iterations > 0 {
346 self.iteration as f64 / self.total_iterations as f64
347 } else {
348 0.0
349 }
350 }
351}
352
353/// Trait for nesting/packing solvers.
354pub trait Solver {
355 /// The geometry type this solver handles.
356 type Geometry: Geometry;
357 /// The boundary type this solver handles.
358 type Boundary: Boundary;
359 /// The scalar type for coordinates.
360 type Scalar;
361
362 /// Solves the nesting/packing problem.
363 fn solve(
364 &self,
365 geometries: &[Self::Geometry],
366 boundary: &Self::Boundary,
367 ) -> Result<SolveResult<Self::Scalar>>;
368
369 /// Solves with a progress callback.
370 fn solve_with_progress(
371 &self,
372 geometries: &[Self::Geometry],
373 boundary: &Self::Boundary,
374 callback: ProgressCallback,
375 ) -> Result<SolveResult<Self::Scalar>>;
376
377 /// Cancels an ongoing solve operation.
378 fn cancel(&self);
379}
380
381#[cfg(test)]
382mod config_tests {
383 use super::Config;
384
385 #[test]
386 fn a_target_utilization_above_one_is_refused_not_clamped() {
387 let config = Config::default().with_target_utilization(1.5);
388 assert_eq!(config.target_utilization, Some(1.5), "stored as given");
389 let err = config.validate().expect_err("1.5 is not a utilization");
390 assert!(err.to_string().contains("target_utilization"), "{err}");
391 assert!(Config::default()
392 .with_target_utilization(0.9)
393 .validate()
394 .is_ok());
395 let nan_rate = Config {
396 mutation_rate: f64::NAN,
397 ..Config::default()
398 };
399 assert!(nan_rate.validate().is_err());
400 }
401
402 /// A budget left unset is the strategy's to choose; one that is set is
403 /// stored as given and judged by `validate`.
404 #[test]
405 fn a_population_is_stored_as_given_and_judged_by_validate() {
406 let unset = Config::default();
407 assert_eq!(unset.population_size, None);
408 assert_eq!(unset.max_generations, None);
409 assert!(unset.validate().is_ok());
410
411 let set = Config::default()
412 .with_population_size(100)
413 .with_max_generations(0);
414 assert_eq!(set.population_size, Some(100));
415 assert_eq!(set.max_generations, Some(0), "0 generations is a budget");
416 assert!(set.validate().is_ok());
417
418 let one = Config::default().with_population_size(1);
419 assert_eq!(one.population_size, Some(1), "stored as given");
420 let err = one.validate().expect_err("a population of 1 cannot cross");
421 assert_eq!(err.code(), "parameter_out_of_range");
422 assert_eq!(
423 err.to_string(),
424 "population_size must be a whole number >= 2, got 1"
425 );
426 }
427}