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

u_nesting_core/
exact.rs
