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]` or a `grid_step`
121    /// that is not finite and positive.
122    pub fn validate(&self) -> crate::error::Result<()> {
123        use crate::error::{check_at_least, check_range};
124        check_range("gap_tolerance", self.gap_tolerance, 0.0, 1.0)?;
125        check_at_least("grid_step", self.grid_step, f64::MIN_POSITIVE)?;
126        Ok(())
127    }
128
129    /// Set maximum number of items for exact solving.
130    pub fn with_max_items(mut self, max: usize) -> Self {
131        self.max_items = max.max(1);
132        self
133    }
134
135    /// Set grid discretization step.
136    pub fn with_grid_step(mut self, step: f64) -> Self {
137        self.grid_step = step.max(0.1);
138        self
139    }
140
141    /// Set number of discrete rotation angles.
142    pub fn with_rotation_steps(mut self, steps: usize) -> Self {
143        self.rotation_steps = steps.max(1);
144        self
145    }
146
147    /// Set verbosity level.
148    pub fn with_verbosity(mut self, level: u32) -> Self {
149        self.verbosity = level;
150        self
151    }
152
153    /// Set random seed for reproducibility.
154    pub fn with_seed(mut self, seed: u64) -> Self {
155        self.seed = Some(seed);
156        self
157    }
158
159    /// Check if the number of items is within the exact solving limit.
160    pub fn is_within_limit(&self, num_items: usize) -> bool {
161        num_items <= self.max_items
162    }
163
164    /// Get discrete rotation angles in radians.
165    pub fn rotation_angles(&self) -> Vec<f64> {
166        let step = std::f64::consts::TAU / self.rotation_steps as f64;
167        (0..self.rotation_steps).map(|i| i as f64 * step).collect()
168    }
169}
170
171/// Extended result information from exact solver.
172#[derive(Debug, Clone, Default)]
173#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
174pub struct ExactResult {
175    /// Solution status.
176    pub status: SolutionStatus,
177
178    /// Best objective value found (lower is better for minimization).
179    pub objective_value: f64,
180
181    /// Best bound on optimal value (for optimality gap calculation).
182    pub best_bound: f64,
183
184    /// Optimality gap: (objective - bound) / objective.
185    pub gap: f64,
186
187    /// Number of branch-and-bound nodes explored.
188    pub nodes_explored: u64,
189
190    /// Number of simplex iterations.
191    pub iterations: u64,
192
193    /// Whether the solution is proven optimal.
194    pub is_optimal: bool,
195
196    /// Solver-specific status message.
197    pub message: String,
198}
199
200impl ExactResult {
201    /// Create a new result with default values.
202    pub fn new() -> Self {
203        Self::default()
204    }
205
206    /// Create a result indicating optimal solution.
207    pub fn optimal(objective: f64) -> Self {
208        Self {
209            status: SolutionStatus::Optimal,
210            objective_value: objective,
211            best_bound: objective,
212            gap: 0.0,
213            is_optimal: true,
214            message: "Optimal solution found".to_string(),
215            ..Default::default()
216        }
217    }
218
219    /// Create a result indicating feasible (but not proven optimal) solution.
220    pub fn feasible(objective: f64, bound: f64) -> Self {
221        let gap = if objective.abs() > 1e-10 {
222            (objective - bound).abs() / objective.abs()
223        } else {
224            0.0
225        };
226        Self {
227            status: SolutionStatus::Feasible,
228            objective_value: objective,
229            best_bound: bound,
230            gap,
231            is_optimal: false,
232            message: format!("Feasible solution found (gap: {:.2}%)", gap * 100.0),
233            ..Default::default()
234        }
235    }
236
237    /// Create a result indicating infeasibility.
238    pub fn infeasible() -> Self {
239        Self {
240            status: SolutionStatus::Infeasible,
241            objective_value: f64::INFINITY,
242            best_bound: f64::INFINITY,
243            is_optimal: false,
244            message: "Problem is infeasible".to_string(),
245            ..Default::default()
246        }
247    }
248
249    /// Create a result indicating timeout.
250    pub fn timeout(best_objective: Option<f64>, best_bound: f64) -> Self {
251        match best_objective {
252            Some(obj) => {
253                let gap = if obj.abs() > 1e-10 {
254                    (obj - best_bound).abs() / obj.abs()
255                } else {
256                    0.0
257                };
258                Self {
259                    status: SolutionStatus::Timeout,
260                    objective_value: obj,
261                    best_bound,
262                    gap,
263                    is_optimal: false,
264                    message: format!("Time limit reached (gap: {:.2}%)", gap * 100.0),
265                    ..Default::default()
266                }
267            }
268            None => Self {
269                status: SolutionStatus::Timeout,
270                objective_value: f64::INFINITY,
271                best_bound,
272                is_optimal: false,
273                message: "Time limit reached without feasible solution".to_string(),
274                ..Default::default()
275            },
276        }
277    }
278
279    /// Create a result indicating an error.
280    pub fn error(message: impl Into<String>) -> Self {
281        Self {
282            status: SolutionStatus::Error,
283            message: message.into(),
284            ..Default::default()
285        }
286    }
287
288    /// Set solver statistics.
289    pub fn with_stats(mut self, nodes: u64, iterations: u64) -> Self {
290        self.nodes_explored = nodes;
291        self.iterations = iterations;
292        self
293    }
294}
295
296#[cfg(test)]
297mod tests {
298    use super::*;
299
300    #[test]
301    fn test_exact_config_default() {
302        let config = ExactConfig::default();
303        assert_eq!(config.time_limit_ms, 60000);
304        assert_eq!(config.gap_tolerance, 0.0);
305        assert_eq!(config.max_items, 15);
306        assert_eq!(config.rotation_steps, 4);
307    }
308
309    #[test]
310    fn test_exact_config_builder() {
311        let config = ExactConfig::new()
312            .with_time_limit_ms(30000)
313            .with_gap_tolerance(0.01)
314            .with_max_items(10)
315            .with_rotation_steps(8)
316            .with_grid_step(0.5);
317
318        assert_eq!(config.time_limit_ms, 30000);
319        assert_eq!(config.gap_tolerance, 0.01);
320        assert_eq!(config.max_items, 10);
321        assert_eq!(config.rotation_steps, 8);
322        assert_eq!(config.grid_step, 0.5);
323    }
324
325    #[test]
326    fn test_rotation_angles() {
327        let config = ExactConfig::default().with_rotation_steps(4);
328        let angles = config.rotation_angles();
329        assert_eq!(angles.len(), 4);
330        assert!((angles[0] - 0.0).abs() < 1e-10);
331        assert!((angles[1] - std::f64::consts::FRAC_PI_2).abs() < 1e-10);
332        assert!((angles[2] - std::f64::consts::PI).abs() < 1e-10);
333    }
334
335    #[test]
336    fn test_is_within_limit() {
337        let config = ExactConfig::default().with_max_items(10);
338        assert!(config.is_within_limit(5));
339        assert!(config.is_within_limit(10));
340        assert!(!config.is_within_limit(11));
341    }
342
343    #[test]
344    fn test_solution_status_display() {
345        assert_eq!(format!("{}", SolutionStatus::Optimal), "Optimal");
346        assert_eq!(format!("{}", SolutionStatus::Feasible), "Feasible");
347        assert_eq!(format!("{}", SolutionStatus::Infeasible), "Infeasible");
348        assert_eq!(format!("{}", SolutionStatus::Timeout), "Timeout");
349    }
350
351    #[test]
352    fn test_exact_result_optimal() {
353        let result = ExactResult::optimal(100.0);
354        assert_eq!(result.status, SolutionStatus::Optimal);
355        assert_eq!(result.objective_value, 100.0);
356        assert_eq!(result.gap, 0.0);
357        assert!(result.is_optimal);
358    }
359
360    #[test]
361    fn test_exact_result_feasible() {
362        let result = ExactResult::feasible(100.0, 95.0);
363        assert_eq!(result.status, SolutionStatus::Feasible);
364        assert_eq!(result.objective_value, 100.0);
365        assert_eq!(result.best_bound, 95.0);
366        assert!((result.gap - 0.05).abs() < 1e-10);
367        assert!(!result.is_optimal);
368    }
369
370    #[test]
371    fn test_exact_result_timeout() {
372        let result = ExactResult::timeout(Some(100.0), 90.0);
373        assert_eq!(result.status, SolutionStatus::Timeout);
374        assert!((result.gap - 0.10).abs() < 1e-10);
375
376        let result_no_solution = ExactResult::timeout(None, 0.0);
377        assert_eq!(result_no_solution.status, SolutionStatus::Timeout);
378        assert_eq!(result_no_solution.objective_value, f64::INFINITY);
379    }
380
381    #[test]
382    fn test_exact_result_with_stats() {
383        let result = ExactResult::optimal(100.0).with_stats(1000, 50000);
384        assert_eq!(result.nodes_explored, 1000);
385        assert_eq!(result.iterations, 50000);
386    }
387}
u_nesting_core/exact.rs

u_nesting_core/
exact.rs
