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

u_nesting_core/
exact.rs
