u_nesting_core/

solver.rs

//! Solver traits and configuration.

use crate::geometry::{Boundary, Geometry};
use crate::result::SolveResult;
use crate::Result;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Optimization strategy.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum Strategy {
    /// Bottom-Left Fill (fast, lower quality).
    #[default]
    BottomLeftFill,
    /// NFP-guided placement (balanced).
    NfpGuided,
    /// Genetic Algorithm (slower, higher quality).
    GeneticAlgorithm,
    /// Biased Random-Key Genetic Algorithm (balanced, robust).
    Brkga,
    /// Simulated Annealing.
    SimulatedAnnealing,
    /// Extreme Point heuristic (3D only).
    ExtremePoint,
    /// Goal-Driven Ruin and Recreate (GDRR).
    Gdrr,
    /// Adaptive Large Neighborhood Search (ALNS).
    Alns,
    /// MILP-based exact solver (small instances, optimal solution).
    MilpExact,
    /// Hybrid: Try exact first, fallback to heuristic on timeout.
    HybridExact,
}

/// The two problem families a strategy runs on: 2D nesting and 3D packing.
/// On the wire (a request's `mode`, the strategy catalog) `"2d"` / `"3d"`.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum Dimension {
    /// 2D nesting of parts on sheets.
    #[cfg_attr(feature = "serde", serde(rename = "2d"))]
    TwoD,
    /// 3D packing of boxes into bins.
    #[cfg_attr(feature = "serde", serde(rename = "3d"))]
    ThreeD,
}

impl Dimension {
    /// The dimension's name on the wire: `"2d"` or `"3d"`.
    pub fn key(self) -> &'static str {
        match self {
            Self::TwoD => "2d",
            Self::ThreeD => "3d",
        }
    }
}

/// The settings a request's `config` can carry besides `strategy`, in the
/// order of `ConfigRequest::KEYS`. Which of them a strategy reads is
/// [`Strategy::reads`].
pub const SETTINGS: [&str; 11] = [
    "spacing",
    "margin",
    "time_limit_ms",
    "target_utilization",
    "population_size",
    "max_generations",
    "max_iterations",
    "crossover_rate",
    "mutation_rate",
    "seed",
    "multi_sheet",
];

/// The short names of the strategies `dimension` offers in this build, joined
/// for a message: `"blf, nfp, ga, ..."` -- what a refusal of a strategy the
/// dimension does not offer lists.
pub fn offered_names(dimension: Dimension) -> String {
    Strategy::offered(dimension)
        .into_iter()
        .map(Strategy::name)
        .collect::<Vec<_>>()
        .join(", ")
}

impl Strategy {
    /// Every strategy, in the order of [`Strategy::NAMES`].
    pub const ALL: [Self; 10] = [
        Self::BottomLeftFill,
        Self::NfpGuided,
        Self::GeneticAlgorithm,
        Self::Brkga,
        Self::SimulatedAnnealing,
        Self::ExtremePoint,
        Self::Gdrr,
        Self::Alns,
        Self::MilpExact,
        Self::HybridExact,
    ];

    /// The strategy's short name -- its entry in [`Strategy::NAMES`].
    pub fn name(self) -> &'static str {
        let index = Self::ALL
            .iter()
            .position(|&s| s == self)
            .expect("ALL lists every strategy");
        Self::NAMES[index]
    }

    /// Whether `dimension` offers this strategy in this build. 2D nesting
    /// offers every strategy but extreme point; the exact strategies only in a
    /// build with the `milp` feature. 3D packing offers bottom-left (layer)
    /// fill, extreme point and the three population/annealing searches.
    pub fn is_offered(self, dimension: Dimension) -> bool {
        use Strategy::*;
        match dimension {
            Dimension::TwoD => {
                self != ExtremePoint
                    && (cfg!(feature = "milp") || !matches!(self, MilpExact | HybridExact))
            }
            Dimension::ThreeD => matches!(
                self,
                BottomLeftFill | ExtremePoint | GeneticAlgorithm | Brkga | SimulatedAnnealing
            ),
        }
    }

    /// The strategies `dimension` offers in this build, in
    /// [`Strategy::NAMES`] order.
    pub fn offered(dimension: Dimension) -> Vec<Self> {
        Self::ALL
            .into_iter()
            .filter(|s| s.is_offered(dimension))
            .collect()
    }

    /// Whether this strategy, run in `dimension`, reads `setting` (one of
    /// [`SETTINGS`]). This is the one table both the refusal of a setting the
    /// strategy does not read (`ConfigRequest::to_config`) and the published
    /// description of each strategy ([`Strategy::reads`]) come from.
    ///
    /// - `spacing`, `margin`, `time_limit_ms`: every strategy.
    /// - `multi_sheet`: every 2D strategy (3D packing has no sheets).
    /// - `crossover_rate`, `mutation_rate`: the genetic algorithm.
    /// - `population_size`, `max_generations`: the two population searches.
    /// - `max_iterations`: the single-solution searches (SA, GDRR, ALNS, and
    ///   the hybrid's ALNS fallback).
    /// - `seed`: the stochastic searches (and the hybrid's ALNS fallback).
    /// - `target_utilization`: the searches that stop on a target (GA, BRKGA,
    ///   SA).
    ///
    /// A name outside [`SETTINGS`] is read by nothing.
    pub fn reads_setting(self, dimension: Dimension, setting: &str) -> bool {
        use Strategy::*;
        match setting {
            "spacing" | "margin" | "time_limit_ms" => true,
            "multi_sheet" => dimension == Dimension::TwoD,
            "crossover_rate" | "mutation_rate" => matches!(self, GeneticAlgorithm),
            "population_size" | "max_generations" => matches!(self, GeneticAlgorithm | Brkga),
            "max_iterations" => matches!(self, SimulatedAnnealing | Gdrr | Alns | HybridExact),
            "seed" => matches!(
                self,
                GeneticAlgorithm | Brkga | SimulatedAnnealing | Gdrr | Alns | HybridExact
            ),
            "target_utilization" => matches!(self, GeneticAlgorithm | Brkga | SimulatedAnnealing),
            _ => false,
        }
    }

    /// The settings this strategy reads in `dimension`, in [`SETTINGS`] order
    /// (see [`Self::reads_setting`]).
    pub fn reads(self, dimension: Dimension) -> Vec<&'static str> {
        SETTINGS
            .into_iter()
            .filter(|s| self.reads_setting(dimension, s))
            .collect()
    }

    /// The names of the strategies `dimension` offers that read `setting`.
    pub fn readers_of(dimension: Dimension, setting: &str) -> Vec<&'static str> {
        Self::offered(dimension)
            .into_iter()
            .filter(|s| s.reads_setting(dimension, setting))
            .map(Self::name)
            .collect()
    }

    /// The short name of each strategy -- what a refusal of an unknown name
    /// lists as expected. [`Strategy::parse`] reads these and the longer
    /// forms in [`Strategy::SPELLINGS`].
    pub const NAMES: [&'static str; 10] = [
        "blf",
        "nfp",
        "ga",
        "brkga",
        "sa",
        "ep",
        "gdrr",
        "alns",
        "milpexact",
        "hybridexact",
    ];

    /// Every spelling [`Strategy::parse`] reads, with the strategy it names:
    /// the [`Strategy::NAMES`] and their longer forms.
    pub const SPELLINGS: [(&'static str, Self); 18] = [
        ("blf", Self::BottomLeftFill),
        ("bottomleftfill", Self::BottomLeftFill),
        ("nfp", Self::NfpGuided),
        ("nfpguided", Self::NfpGuided),
        ("ga", Self::GeneticAlgorithm),
        ("genetic", Self::GeneticAlgorithm),
        ("geneticalgorithm", Self::GeneticAlgorithm),
        ("brkga", Self::Brkga),
        ("sa", Self::SimulatedAnnealing),
        ("simulatedannealing", Self::SimulatedAnnealing),
        ("ep", Self::ExtremePoint),
        ("extremepoint", Self::ExtremePoint),
        ("gdrr", Self::Gdrr),
        ("alns", Self::Alns),
        ("milpexact", Self::MilpExact),
        ("exact", Self::MilpExact),
        ("hybridexact", Self::HybridExact),
        ("hybrid", Self::HybridExact),
    ];

    /// Parses a strategy name (case-insensitive, whitespace-trimmed).
    ///
    /// Returns `None` for unrecognized names so callers surface an explicit
    /// error instead of silently falling back to a default strategy (which
    /// hides typos from consumers). This is the single source of truth for
    /// strategy-name parsing across all bindings (C FFI, Python, WASM).
    pub fn parse(name: &str) -> Option<Self> {
        let name = name.trim().to_lowercase();
        Self::SPELLINGS
            .iter()
            .find(|(spelling, _)| *spelling == name)
            .map(|&(_, strategy)| strategy)
    }
}

/// Common configuration for solvers.
///
/// It holds no thread count: a build with the `parallel` feature runs its
/// parallel work on the rayon pool the solve is called from, so
/// `rayon::ThreadPool::install` around the solve (or `RAYON_NUM_THREADS`)
/// bounds it; without the feature a solve runs on the calling thread.
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Config {
    /// Optimization strategy.
    pub strategy: Strategy,

    /// Minimum distance between any two placed geometries. It does not apply
    /// between a geometry and the boundary — that is `margin`.
    pub spacing: f64,

    /// Minimum distance between any placed geometry and the boundary edge.
    pub margin: f64,

    /// Maximum computation time in milliseconds (0 = unlimited).
    ///
    /// The search strategies check it between individual placements, so a solve
    /// returns within the limit plus the time of the greedy bottom-left pass it is
    /// compared against. The layout returned is the best one found in that time.
    pub time_limit_ms: u64,

    /// Target utilization (0.0 - 1.0). Solver stops if reached.
    pub target_utilization: Option<f64>,

    // GA-specific parameters
    /// Population size for the population-based strategies (GA, BRKGA).
    ///
    /// `None` runs each strategy with the size it is tuned for -- 2D GA and
    /// BRKGA 30, 3D GA 100, 3D BRKGA 50; `Some(n)` runs it with `n`, at least
    /// 2. The other strategies have no population and do not read it.
    pub population_size: Option<usize>,

    /// Generation budget for the population-based strategies (GA, BRKGA).
    ///
    /// `None` runs each strategy with the budget it is tuned for -- 2D GA and
    /// BRKGA 50, 3D GA 500, 3D BRKGA 100; `Some(n)` allows `n` generations (0
    /// evaluates the first population only). A run also ends on the time
    /// limit, on cancellation and when the best layout stops improving.
    pub max_generations: Option<u32>,

    /// Iteration budget for the single-solution searches (SA, GDRR, ALNS).
    ///
    /// `None` runs each with the budget it is tuned for -- 2D SA 500, GDRR
    /// and ALNS 1000, 3D SA 10000; `Some(n)` allows `n` iterations (at least
    /// one). A seeded run that ends on this budget, not on the clock, is
    /// reproduced exactly (see [`Config::seed`]). A run also ends on the time
    /// limit and on cancellation, and SA when it has cooled.
    pub max_iterations: Option<u64>,

    /// Crossover rate for GA (0.0 - 1.0).
    pub crossover_rate: f64,

    /// Mutation rate for GA (0.0 - 1.0).
    pub mutation_rate: f64,

    /// Elite count for GA.
    pub elite_count: usize,

    /// Optional RNG seed for reproducible runs of the stochastic strategies
    /// (GA, BRKGA, SA, GDRR, ALNS -- 2D and 3D). `None` seeds from system
    /// entropy (non-deterministic).
    ///
    /// A seeded run draws every random choice from the seed, so the same
    /// request with the same seed returns the same layout **when the run ends
    /// on its own budget** -- the generation or iteration count, convergence,
    /// or the target utilization. A run cut short by the clock is not
    /// reproduced: how far a search gets before `time_limit_ms` (or a
    /// cancellation) stops it depends on the machine and its load. With
    /// `time_limit_ms` 0 a search runs to its own budget (`max_generations`,
    /// `max_iterations`), so a seeded unlimited run is always reproduced.
    pub seed: Option<u64>,
}

impl Default for Config {
    fn default() -> Self {
        Self {
            strategy: Strategy::default(),
            spacing: 0.0,
            margin: 0.0,
            time_limit_ms: 30000,
            target_utilization: None,
            population_size: None,
            max_generations: None,
            max_iterations: None,
            crossover_rate: 0.85,
            mutation_rate: 0.05,
            elite_count: 5,
            seed: None,
        }
    }
}

impl Config {
    /// Creates a new configuration with default values.
    pub fn new() -> Self {
        Self::default()
    }

    /// Checks the fields a caller sets against their ranges -- the builders
    /// store what they are given, and every solver calls this before it runs.
    ///
    /// # Errors
    /// `ConfigError` naming the first field out of range: `spacing` or
    /// `margin` negative or not finite, `crossover_rate`/`mutation_rate` or
    /// `target_utilization` outside `[0, 1]`, a `population_size` set below 2,
    /// a `max_iterations` set to 0.
    pub fn validate(&self) -> Result<()> {
        use crate::error::{check_at_least, check_range};
        check_at_least("spacing", self.spacing, 0.0)?;
        check_at_least("margin", self.margin, 0.0)?;
        if let Some(size) = self.population_size {
            Self::check_population_size(size as i128)?;
        }
        if let Some(iterations) = self.max_iterations {
            Self::check_max_iterations(i128::from(iterations))?;
        }
        check_range("crossover_rate", self.crossover_rate, 0.0, 1.0)?;
        check_range("mutation_rate", self.mutation_rate, 0.0, 1.0)?;
        if let Some(util) = self.target_utilization {
            check_range("target_utilization", util, 0.0, 1.0)?;
        }
        Ok(())
    }

    /// A population size: at least 2, the fewest a generation can cross. A
    /// request's value and a configuration's own are judged here alike.
    pub(crate) fn check_population_size(value: i128) -> Result<usize> {
        crate::error::whole_at_least("population_size", value, 2)
    }

    /// An iteration budget: at least 1. A request's value and a
    /// configuration's own are judged here alike.
    pub(crate) fn check_max_iterations(value: i128) -> Result<u64> {
        crate::error::whole_at_least("max_iterations", value, 1)
    }

    /// Sets the optimization strategy.
    pub fn with_strategy(mut self, strategy: Strategy) -> Self {
        self.strategy = strategy;
        self
    }

    /// Sets the spacing between geometries.
    pub fn with_spacing(mut self, spacing: f64) -> Self {
        self.spacing = spacing;
        self
    }

    /// Sets the margin from boundary edges.
    pub fn with_margin(mut self, margin: f64) -> Self {
        self.margin = margin;
        self
    }

    /// Sets the time limit in milliseconds.
    pub fn with_time_limit(mut self, ms: u64) -> Self {
        self.time_limit_ms = ms;
        self
    }

    /// Sets the target utilization.
    pub fn with_target_utilization(mut self, util: f64) -> Self {
        self.target_utilization = Some(util);
        self
    }

    /// Sets the RNG seed for reproducible stochastic runs (see [`Config::seed`]).
    pub fn with_seed(mut self, seed: u64) -> Self {
        self.seed = Some(seed);
        self
    }

    /// Sets the population size of the population-based strategies, in place
    /// of each strategy's own (see [`Config::population_size`]).
    pub fn with_population_size(mut self, size: usize) -> Self {
        self.population_size = Some(size);
        self
    }

    /// Sets the generation budget of the population-based strategies, in
    /// place of each strategy's own (see [`Config::max_generations`]).
    pub fn with_max_generations(mut self, generations: u32) -> Self {
        self.max_generations = Some(generations);
        self
    }

    /// Sets the iteration budget of the single-solution searches, in place
    /// of each strategy's own (see [`Config::max_iterations`]).
    pub fn with_max_iterations(mut self, iterations: u64) -> Self {
        self.max_iterations = Some(iterations);
        self
    }
}

/// Progress callback for long-running operations.
pub type ProgressCallback = Box<dyn Fn(ProgressInfo) + Send + Sync>;

/// Progress information during solving.
#[derive(Debug, Clone, Default)]
pub struct ProgressInfo {
    /// Current iteration/generation number.
    pub iteration: u32,
    /// Total expected iterations (0 if unknown).
    pub total_iterations: u32,
    /// Current best utilization (0.0 to 1.0).
    pub utilization: f64,
    /// Current best fitness value.
    pub best_fitness: f64,
    /// Number of items placed.
    pub items_placed: usize,
    /// Total number of items.
    pub total_items: usize,
    /// Elapsed time in milliseconds.
    pub elapsed_ms: u64,
    /// Current phase/stage description.
    pub phase: String,
    /// Whether the solver is still running.
    pub running: bool,
}

impl ProgressInfo {
    /// Creates a new progress info with default values.
    pub fn new() -> Self {
        Self {
            running: true,
            ..Default::default()
        }
    }

    /// Sets the iteration info.
    pub fn with_iteration(mut self, current: u32, total: u32) -> Self {
        self.iteration = current;
        self.total_iterations = total;
        self
    }

    /// Sets the utilization.
    pub fn with_utilization(mut self, utilization: f64) -> Self {
        self.utilization = utilization;
        self
    }

    /// Sets the best fitness.
    pub fn with_fitness(mut self, fitness: f64) -> Self {
        self.best_fitness = fitness;
        self
    }

    /// Sets the items placed info.
    pub fn with_items(mut self, placed: usize, total: usize) -> Self {
        self.items_placed = placed;
        self.total_items = total;
        self
    }

    /// Sets the elapsed time.
    pub fn with_elapsed(mut self, elapsed_ms: u64) -> Self {
        self.elapsed_ms = elapsed_ms;
        self
    }

    /// Sets the phase description.
    pub fn with_phase(mut self, phase: impl Into<String>) -> Self {
        self.phase = phase.into();
        self
    }

    /// One step of a search: step `iteration` of `total` (0 when unknown),
    /// the best fitness so far, the time since the search began and its
    /// `phase` -- finished when the search is no longer `running`.
    pub fn search_step(
        phase: &str,
        iteration: u64,
        total: u64,
        best_fitness: f64,
        elapsed_ms: u64,
        running: bool,
    ) -> Self {
        let narrow = |n: u64| u32::try_from(n).unwrap_or(u32::MAX);
        let info = Self::new()
            .with_iteration(narrow(iteration), narrow(total))
            .with_fitness(best_fitness)
            .with_elapsed(elapsed_ms)
            .with_phase(phase);
        if running {
            info
        } else {
            info.finished()
        }
    }

    /// Marks the solver as finished.
    pub fn finished(mut self) -> Self {
        self.running = false;
        self
    }

    /// Calculates the progress percentage (0.0 to 1.0).
    pub fn progress_percent(&self) -> f64 {
        if self.total_iterations > 0 {
            self.iteration as f64 / self.total_iterations as f64
        } else {
            0.0
        }
    }
}

/// Trait for nesting/packing solvers.
pub trait Solver {
    /// The geometry type this solver handles.
    type Geometry: Geometry;
    /// The boundary type this solver handles.
    type Boundary: Boundary;
    /// The scalar type for coordinates.
    type Scalar;

    /// Solves the nesting/packing problem.
    fn solve(
        &self,
        geometries: &[Self::Geometry],
        boundary: &Self::Boundary,
    ) -> Result<SolveResult<Self::Scalar>>;

    /// Solves with a progress callback.
    fn solve_with_progress(
        &self,
        geometries: &[Self::Geometry],
        boundary: &Self::Boundary,
        callback: ProgressCallback,
    ) -> Result<SolveResult<Self::Scalar>>;

    /// Cancels an ongoing solve operation.
    fn cancel(&self);
}

#[cfg(test)]
mod config_tests {
    use super::Config;

    #[test]
    fn a_target_utilization_above_one_is_refused_not_clamped() {
        let config = Config::default().with_target_utilization(1.5);
        assert_eq!(config.target_utilization, Some(1.5), "stored as given");
        let err = config.validate().expect_err("1.5 is not a utilization");
        assert!(err.to_string().contains("target_utilization"), "{err}");
        assert!(Config::default()
            .with_target_utilization(0.9)
            .validate()
            .is_ok());
        let nan_rate = Config {
            mutation_rate: f64::NAN,
            ..Config::default()
        };
        assert!(nan_rate.validate().is_err());
    }

    /// A budget left unset is the strategy's to choose; one that is set is
    /// stored as given and judged by `validate`.
    #[test]
    fn a_population_is_stored_as_given_and_judged_by_validate() {
        let unset = Config::default();
        assert_eq!(unset.population_size, None);
        assert_eq!(unset.max_generations, None);
        assert!(unset.validate().is_ok());

        let set = Config::default()
            .with_population_size(100)
            .with_max_generations(0);
        assert_eq!(set.population_size, Some(100));
        assert_eq!(set.max_generations, Some(0), "0 generations is a budget");
        assert!(set.validate().is_ok());

        let one = Config::default().with_population_size(1);
        assert_eq!(one.population_size, Some(1), "stored as given");
        let err = one.validate().expect_err("a population of 1 cannot cross");
        assert_eq!(err.code(), "parameter_out_of_range");
        assert_eq!(
            err.to_string(),
            "population_size must be a whole number >= 2, got 1"
        );
    }
}