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_max_items(10);
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    /// Maximum number of items for exact solving (fallback to heuristic if exceeded).
66    pub max_items: usize,
67
68    /// Grid discretization step for position variables.
69    pub grid_step: f64,
70
71    /// Number of discrete rotation angles to consider.
72    pub rotation_steps: usize,
73}
74
75impl Default for ExactConfig {
76    fn default() -> Self {
77        Self {
78            time_limit_ms: 60000, // 1 minute default
79            max_items: 15,        // Small instances only
80            grid_step: 1.0,       // 1 unit grid
81            rotation_steps: 4,    // 0, 90, 180, 270 degrees
82        }
83    }
84}
85
86impl ExactConfig {
87    /// Create a new configuration with default values.
88    pub fn new() -> Self {
89        Self::default()
90    }
91
92    /// Set time limit in milliseconds.
93    pub fn with_time_limit_ms(mut self, ms: u64) -> Self {
94        self.time_limit_ms = ms;
95        self
96    }
97
98    /// Checks every field against its range; the builders store what they are
99    /// given.
100    ///
101    /// # Errors
102    /// `ConfigError` for a `grid_step` that is not finite and positive, or a
103    /// `max_items` or `rotation_steps` below 1.
104    pub fn validate(&self) -> crate::error::Result<()> {
105        use crate::error::{check_above, check_at_least};
106        check_above("grid_step", self.grid_step, 0.0)?;
107        check_at_least("max_items", self.max_items as f64, 1.0)?;
108        check_at_least("rotation_steps", self.rotation_steps as f64, 1.0)?;
109        Ok(())
110    }
111
112    /// Set maximum number of items for exact solving.
113    pub fn with_max_items(mut self, max: usize) -> Self {
114        self.max_items = max;
115        self
116    }
117
118    /// Set grid discretization step.
119    pub fn with_grid_step(mut self, step: f64) -> Self {
120        self.grid_step = step;
121        self
122    }
123
124    /// Set number of discrete rotation angles.
125    pub fn with_rotation_steps(mut self, steps: usize) -> Self {
126        self.rotation_steps = steps;
127        self
128    }
129
130    /// Check if the number of items is within the exact solving limit.
131    pub fn is_within_limit(&self, num_items: usize) -> bool {
132        num_items <= self.max_items
133    }
134
135    /// Get discrete rotation angles in radians.
136    pub fn rotation_angles(&self) -> Vec<f64> {
137        let step = std::f64::consts::TAU / self.rotation_steps as f64;
138        (0..self.rotation_steps).map(|i| i as f64 * step).collect()
139    }
140}
141
142/// Extended result information from exact solver.
143#[derive(Debug, Clone, Default)]
144#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
145pub struct ExactResult {
146    /// Solution status.
147    pub status: SolutionStatus,
148
149    /// Best objective value found (lower is better for minimization).
150    pub objective_value: f64,
151
152    /// Best bound on optimal value (for optimality gap calculation).
153    pub best_bound: f64,
154
155    /// Optimality gap: (objective - bound) / objective.
156    pub gap: f64,
157
158    /// Number of branch-and-bound nodes explored.
159    pub nodes_explored: u64,
160
161    /// Number of simplex iterations.
162    pub iterations: u64,
163
164    /// Whether the solution is proven optimal.
165    pub is_optimal: bool,
166
167    /// Solver-specific status message.
168    pub message: String,
169}
170
171impl ExactResult {
172    /// Create a new result with default values.
173    pub fn new() -> Self {
174        Self::default()
175    }
176
177    /// Create a result indicating optimal solution.
178    pub fn optimal(objective: f64) -> Self {
179        Self {
180            status: SolutionStatus::Optimal,
181            objective_value: objective,
182            best_bound: objective,
183            gap: 0.0,
184            is_optimal: true,
185            message: "Optimal solution found".to_string(),
186            ..Default::default()
187        }
188    }
189
190    /// Create a result indicating feasible (but not proven optimal) solution.
191    pub fn feasible(objective: f64, bound: f64) -> Self {
192        let gap = if objective.abs() > 1e-10 {
193            (objective - bound).abs() / objective.abs()
194        } else {
195            0.0
196        };
197        Self {
198            status: SolutionStatus::Feasible,
199            objective_value: objective,
200            best_bound: bound,
201            gap,
202            is_optimal: false,
203            message: format!("Feasible solution found (gap: {:.2}%)", gap * 100.0),
204            ..Default::default()
205        }
206    }
207
208    /// Create a result indicating infeasibility.
209    pub fn infeasible() -> Self {
210        Self {
211            status: SolutionStatus::Infeasible,
212            objective_value: f64::INFINITY,
213            best_bound: f64::INFINITY,
214            is_optimal: false,
215            message: "Problem is infeasible".to_string(),
216            ..Default::default()
217        }
218    }
219
220    /// Create a result indicating timeout.
221    pub fn timeout(best_objective: Option<f64>, best_bound: f64) -> Self {
222        match best_objective {
223            Some(obj) => {
224                let gap = if obj.abs() > 1e-10 {
225                    (obj - best_bound).abs() / obj.abs()
226                } else {
227                    0.0
228                };
229                Self {
230                    status: SolutionStatus::Timeout,
231                    objective_value: obj,
232                    best_bound,
233                    gap,
234                    is_optimal: false,
235                    message: format!("Time limit reached (gap: {:.2}%)", gap * 100.0),
236                    ..Default::default()
237                }
238            }
239            None => Self {
240                status: SolutionStatus::Timeout,
241                objective_value: f64::INFINITY,
242                best_bound,
243                is_optimal: false,
244                message: "Time limit reached without feasible solution".to_string(),
245                ..Default::default()
246            },
247        }
248    }
249
250    /// Create a result indicating an error.
251    pub fn error(message: impl Into<String>) -> Self {
252        Self {
253            status: SolutionStatus::Error,
254            message: message.into(),
255            ..Default::default()
256        }
257    }
258
259    /// Set solver statistics.
260    pub fn with_stats(mut self, nodes: u64, iterations: u64) -> Self {
261        self.nodes_explored = nodes;
262        self.iterations = iterations;
263        self
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270
271    #[test]
272    fn test_exact_config_default() {
273        let config = ExactConfig::default();
274        assert_eq!(config.time_limit_ms, 60000);
275        assert_eq!(config.max_items, 15);
276        assert_eq!(config.rotation_steps, 4);
277    }
278
279    #[test]
280    fn test_exact_config_builder() {
281        let config = ExactConfig::new()
282            .with_time_limit_ms(30000)
283            .with_max_items(10)
284            .with_rotation_steps(8)
285            .with_grid_step(0.5);
286
287        assert_eq!(config.time_limit_ms, 30000);
288        assert_eq!(config.max_items, 10);
289        assert_eq!(config.rotation_steps, 8);
290        assert_eq!(config.grid_step, 0.5);
291    }
292
293    #[test]
294    fn test_rotation_angles() {
295        let config = ExactConfig::default().with_rotation_steps(4);
296        let angles = config.rotation_angles();
297        assert_eq!(angles.len(), 4);
298        assert!((angles[0] - 0.0).abs() < 1e-10);
299        assert!((angles[1] - std::f64::consts::FRAC_PI_2).abs() < 1e-10);
300        assert!((angles[2] - std::f64::consts::PI).abs() < 1e-10);
301    }
302
303    #[test]
304    fn test_is_within_limit() {
305        let config = ExactConfig::default().with_max_items(10);
306        assert!(config.is_within_limit(5));
307        assert!(config.is_within_limit(10));
308        assert!(!config.is_within_limit(11));
309    }
310
311    #[test]
312    fn test_solution_status_display() {
313        assert_eq!(format!("{}", SolutionStatus::Optimal), "Optimal");
314        assert_eq!(format!("{}", SolutionStatus::Feasible), "Feasible");
315        assert_eq!(format!("{}", SolutionStatus::Infeasible), "Infeasible");
316        assert_eq!(format!("{}", SolutionStatus::Timeout), "Timeout");
317    }
318
319    #[test]
320    fn test_exact_result_optimal() {
321        let result = ExactResult::optimal(100.0);
322        assert_eq!(result.status, SolutionStatus::Optimal);
323        assert_eq!(result.objective_value, 100.0);
324        assert_eq!(result.gap, 0.0);
325        assert!(result.is_optimal);
326    }
327
328    #[test]
329    fn test_exact_result_feasible() {
330        let result = ExactResult::feasible(100.0, 95.0);
331        assert_eq!(result.status, SolutionStatus::Feasible);
332        assert_eq!(result.objective_value, 100.0);
333        assert_eq!(result.best_bound, 95.0);
334        assert!((result.gap - 0.05).abs() < 1e-10);
335        assert!(!result.is_optimal);
336    }
337
338    #[test]
339    fn test_exact_result_timeout() {
340        let result = ExactResult::timeout(Some(100.0), 90.0);
341        assert_eq!(result.status, SolutionStatus::Timeout);
342        assert!((result.gap - 0.10).abs() < 1e-10);
343
344        let result_no_solution = ExactResult::timeout(None, 0.0);
345        assert_eq!(result_no_solution.status, SolutionStatus::Timeout);
346        assert_eq!(result_no_solution.objective_value, f64::INFINITY);
347    }
348
349    #[test]
350    fn test_exact_result_with_stats() {
351        let result = ExactResult::optimal(100.0).with_stats(1000, 50000);
352        assert_eq!(result.nodes_explored, 1000);
353        assert_eq!(result.iterations, 50000);
354    }
355}
u_nesting_core/exact.rs

u_nesting_core/
exact.rs
