u_nesting_core/
exact.rs

1//! Exact solver configuration and result types.
2//!
3//! This module provides types for MILP-based exact solving of small nesting instances.
4//! Exact solvers guarantee optimal solutions but are computationally expensive,
5//! making them suitable only for small instances (typically ≤15-20 pieces).
6//!
7//! # Features
8//!
9//! - `ExactConfig`: Configuration for exact solvers (time limits, gap tolerance)
10//! - `ExactResult`: Extended result with optimality proof information
11//! - `SolutionStatus`: Optimal, Feasible, Infeasible, or Timeout
12//!
13//! # Example
14//!
15//! ```ignore
16//! use u_nesting_core::exact::{ExactConfig, SolutionStatus};
17//!
18//! let config = ExactConfig::default()
19//!     .with_time_limit_ms(60000)  // 1 minute
20//!     .with_gap_tolerance(0.01);  // 1% optimality gap
21//! ```
22
23#[cfg(feature = "serde")]
24use serde::{Deserialize, Serialize};
25
26/// Solution status from exact solver.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
28#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
29pub enum SolutionStatus {
30    /// Proven optimal solution found.
31    Optimal,
32    /// Feasible solution found, but optimality not proven.
33    Feasible,
34    /// Problem is infeasible (no valid placement exists).
35    Infeasible,
36    /// Time limit reached without finding any feasible solution.
37    Timeout,
38    /// Solver encountered an error.
39    Error,
40    /// Solution status unknown or not applicable.
41    #[default]
42    Unknown,
43}
44
45impl std::fmt::Display for SolutionStatus {
46    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
47        match self {
48            Self::Optimal => write!(f, "Optimal"),
49            Self::Feasible => write!(f, "Feasible"),
50            Self::Infeasible => write!(f, "Infeasible"),
51            Self::Timeout => write!(f, "Timeout"),
52            Self::Error => write!(f, "Error"),
53            Self::Unknown => write!(f, "Unknown"),
54        }
55    }
56}
57
58/// Configuration for exact (MILP-based) solvers.
59#[derive(Debug, Clone)]
60#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
61pub struct ExactConfig {
62    /// Maximum computation time in milliseconds.
63    pub time_limit_ms: u64,
64
65    /// Relative MIP gap tolerance (0.0 = optimal, 0.01 = 1% gap allowed).
66    pub gap_tolerance: f64,
67
68    /// Maximum number of items for exact solving (fallback to heuristic if exceeded).
69    pub max_items: usize,
70
71    /// Grid discretization step for position variables.
72    pub grid_step: f64,
73
74    /// Number of discrete rotation angles to consider.
75    pub rotation_steps: usize,
76
77    /// Verbosity level (0 = silent, 1 = summary, 2+ = detailed).
78    pub verbosity: u32,
79
80    /// Random seed for reproducibility.
81    pub seed: Option<u64>,
82}
83
84impl Default for ExactConfig {
85    fn default() -> Self {
86        Self {
87            time_limit_ms: 60000, // 1 minute default
88            gap_tolerance: 0.0,   // Require optimal
89            max_items: 15,        // Small instances only
90            grid_step: 1.0,       // 1 unit grid
91            rotation_steps: 4,    // 0, 90, 180, 270 degrees
92            verbosity: 0,
93            seed: None,
94        }
95    }
96}
97
98impl ExactConfig {
99    /// Create a new configuration with default values.
100    pub fn new() -> Self {
101        Self::default()
102    }
103
104    /// Set time limit in milliseconds.
105    pub fn with_time_limit_ms(mut self, ms: u64) -> Self {
106        self.time_limit_ms = ms;
107        self
108    }
109
110    /// Set MIP gap tolerance.
111    pub fn with_gap_tolerance(mut self, gap: f64) -> Self {
112        self.gap_tolerance = gap;
113        self
114    }
115
116    /// Checks every field against its range; the builders store what they are
117    /// given.
118    ///
119    /// # Errors
120    /// `ConfigError` for a `gap_tolerance` outside `[0, 1]`, a `grid_step`
121    /// that is not finite and positive, or a `max_items` or `rotation_steps`
122    /// below 1.
123    pub fn validate(&self) -> crate::error::Result<()> {
124        use crate::error::{check_above, check_at_least, check_range};
125        check_range("gap_tolerance", self.gap_tolerance, 0.0, 1.0)?;
126        check_above("grid_step", self.grid_step, 0.0)?;
127        check_at_least("max_items", self.max_items as f64, 1.0)?;
128        check_at_least("rotation_steps", self.rotation_steps as f64, 1.0)?;
129        Ok(())
130    }
131
132    /// Set maximum number of items for exact solving.
133    pub fn with_max_items(mut self, max: usize) -> Self {
134        self.max_items = max;
135        self
136    }
137
138    /// Set grid discretization step.
139    pub fn with_grid_step(mut self, step: f64) -> Self {
140        self.grid_step = step;
141        self
142    }
143
144    /// Set number of discrete rotation angles.
145    pub fn with_rotation_steps(mut self, steps: usize) -> Self {
146        self.rotation_steps = steps;
147        self
148    }
149
150    /// Set verbosity level.
151    pub fn with_verbosity(mut self, level: u32) -> Self {
152        self.verbosity = level;
153        self
154    }
155
156    /// Set random seed for reproducibility.
157    pub fn with_seed(mut self, seed: u64) -> Self {
158        self.seed = Some(seed);
159        self
160    }
161
162    /// Check if the number of items is within the exact solving limit.
163    pub fn is_within_limit(&self, num_items: usize) -> bool {
164        num_items <= self.max_items
165    }
166
167    /// Get discrete rotation angles in radians.
168    pub fn rotation_angles(&self) -> Vec<f64> {
169        let step = std::f64::consts::TAU / self.rotation_steps as f64;
170        (0..self.rotation_steps).map(|i| i as f64 * step).collect()
171    }
172}
173
174/// Extended result information from exact solver.
175#[derive(Debug, Clone, Default)]
176#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
177pub struct ExactResult {
178    /// Solution status.
179    pub status: SolutionStatus,
180
181    /// Best objective value found (lower is better for minimization).
182    pub objective_value: f64,
183
184    /// Best bound on optimal value (for optimality gap calculation).
185    pub best_bound: f64,
186
187    /// Optimality gap: (objective - bound) / objective.
188    pub gap: f64,
189
190    /// Number of branch-and-bound nodes explored.
191    pub nodes_explored: u64,
192
193    /// Number of simplex iterations.
194    pub iterations: u64,
195
196    /// Whether the solution is proven optimal.
197    pub is_optimal: bool,
198
199    /// Solver-specific status message.
200    pub message: String,
201}
202
203impl ExactResult {
204    /// Create a new result with default values.
205    pub fn new() -> Self {
206        Self::default()
207    }
208
209    /// Create a result indicating optimal solution.
210    pub fn optimal(objective: f64) -> Self {
211        Self {
212            status: SolutionStatus::Optimal,
213            objective_value: objective,
214            best_bound: objective,
215            gap: 0.0,
216            is_optimal: true,
217            message: "Optimal solution found".to_string(),
218            ..Default::default()
219        }
220    }
221
222    /// Create a result indicating feasible (but not proven optimal) solution.
223    pub fn feasible(objective: f64, bound: f64) -> Self {
224        let gap = if objective.abs() > 1e-10 {
225            (objective - bound).abs() / objective.abs()
226        } else {
227            0.0
228        };
229        Self {
230            status: SolutionStatus::Feasible,
231            objective_value: objective,
232            best_bound: bound,
233            gap,
234            is_optimal: false,
235            message: format!("Feasible solution found (gap: {:.2}%)", gap * 100.0),
236            ..Default::default()
237        }
238    }
239
240    /// Create a result indicating infeasibility.
241    pub fn infeasible() -> Self {
242        Self {
243            status: SolutionStatus::Infeasible,
244            objective_value: f64::INFINITY,
245            best_bound: f64::INFINITY,
246            is_optimal: false,
247            message: "Problem is infeasible".to_string(),
248            ..Default::default()
249        }
250    }
251
252    /// Create a result indicating timeout.
253    pub fn timeout(best_objective: Option<f64>, best_bound: f64) -> Self {
254        match best_objective {
255            Some(obj) => {
256                let gap = if obj.abs() > 1e-10 {
257                    (obj - best_bound).abs() / obj.abs()
258                } else {
259                    0.0
260                };
261                Self {
262                    status: SolutionStatus::Timeout,
263                    objective_value: obj,
264                    best_bound,
265                    gap,
266                    is_optimal: false,
267                    message: format!("Time limit reached (gap: {:.2}%)", gap * 100.0),
268                    ..Default::default()
269                }
270            }
271            None => Self {
272                status: SolutionStatus::Timeout,
273                objective_value: f64::INFINITY,
274                best_bound,
275                is_optimal: false,
276                message: "Time limit reached without feasible solution".to_string(),
277                ..Default::default()
278            },
279        }
280    }
281
282    /// Create a result indicating an error.
283    pub fn error(message: impl Into<String>) -> Self {
284        Self {
285            status: SolutionStatus::Error,
286            message: message.into(),
287            ..Default::default()
288        }
289    }
290
291    /// Set solver statistics.
292    pub fn with_stats(mut self, nodes: u64, iterations: u64) -> Self {
293        self.nodes_explored = nodes;
294        self.iterations = iterations;
295        self
296    }
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302
303    #[test]
304    fn test_exact_config_default() {
305        let config = ExactConfig::default();
306        assert_eq!(config.time_limit_ms, 60000);
307        assert_eq!(config.gap_tolerance, 0.0);
308        assert_eq!(config.max_items, 15);
309        assert_eq!(config.rotation_steps, 4);
310    }
311
312    #[test]
313    fn test_exact_config_builder() {
314        let config = ExactConfig::new()
315            .with_time_limit_ms(30000)
316            .with_gap_tolerance(0.01)
317            .with_max_items(10)
318            .with_rotation_steps(8)
319            .with_grid_step(0.5);
320
321        assert_eq!(config.time_limit_ms, 30000);
322        assert_eq!(config.gap_tolerance, 0.01);
323        assert_eq!(config.max_items, 10);
324        assert_eq!(config.rotation_steps, 8);
325        assert_eq!(config.grid_step, 0.5);
326    }
327
328    #[test]
329    fn test_rotation_angles() {
330        let config = ExactConfig::default().with_rotation_steps(4);
331        let angles = config.rotation_angles();
332        assert_eq!(angles.len(), 4);
333        assert!((angles[0] - 0.0).abs() < 1e-10);
334        assert!((angles[1] - std::f64::consts::FRAC_PI_2).abs() < 1e-10);
335        assert!((angles[2] - std::f64::consts::PI).abs() < 1e-10);
336    }
337
338    #[test]
339    fn test_is_within_limit() {
340        let config = ExactConfig::default().with_max_items(10);
341        assert!(config.is_within_limit(5));
342        assert!(config.is_within_limit(10));
343        assert!(!config.is_within_limit(11));
344    }
345
346    #[test]
347    fn test_solution_status_display() {
348        assert_eq!(format!("{}", SolutionStatus::Optimal), "Optimal");
349        assert_eq!(format!("{}", SolutionStatus::Feasible), "Feasible");
350        assert_eq!(format!("{}", SolutionStatus::Infeasible), "Infeasible");
351        assert_eq!(format!("{}", SolutionStatus::Timeout), "Timeout");
352    }
353
354    #[test]
355    fn test_exact_result_optimal() {
356        let result = ExactResult::optimal(100.0);
357        assert_eq!(result.status, SolutionStatus::Optimal);
358        assert_eq!(result.objective_value, 100.0);
359        assert_eq!(result.gap, 0.0);
360        assert!(result.is_optimal);
361    }
362
363    #[test]
364    fn test_exact_result_feasible() {
365        let result = ExactResult::feasible(100.0, 95.0);
366        assert_eq!(result.status, SolutionStatus::Feasible);
367        assert_eq!(result.objective_value, 100.0);
368        assert_eq!(result.best_bound, 95.0);
369        assert!((result.gap - 0.05).abs() < 1e-10);
370        assert!(!result.is_optimal);
371    }
372
373    #[test]
374    fn test_exact_result_timeout() {
375        let result = ExactResult::timeout(Some(100.0), 90.0);
376        assert_eq!(result.status, SolutionStatus::Timeout);
377        assert!((result.gap - 0.10).abs() < 1e-10);
378
379        let result_no_solution = ExactResult::timeout(None, 0.0);
380        assert_eq!(result_no_solution.status, SolutionStatus::Timeout);
381        assert_eq!(result_no_solution.objective_value, f64::INFINITY);
382    }
383
384    #[test]
385    fn test_exact_result_with_stats() {
386        let result = ExactResult::optimal(100.0).with_stats(1000, 50000);
387        assert_eq!(result.nodes_explored, 1000);
388        assert_eq!(result.iterations, 50000);
389    }
390}
u_nesting_core/exact.rs

u_nesting_core/
exact.rs
