solverforge_solver/phase/exhaustive/
bounder.rs

1//! Score bounder for exhaustive search pruning.
2//!
3//! Bounders calculate optimistic and pessimistic score bounds
4//! that enable branch-and-bound pruning.
5
6use std::fmt::Debug;
7
8use solverforge_core::domain::PlanningSolution;
9use solverforge_scoring::ScoreDirector;
10
11/// Calculates score bounds for exhaustive search pruning.
12///
13/// The bounder estimates the best possible score that can be achieved
14/// from a partial solution state. If this optimistic bound is worse than
15/// the best complete solution found so far, the branch can be pruned.
16pub trait ScoreBounder<S: PlanningSolution, D: ScoreDirector<S>>: Send + Debug {
17    /// Calculates the optimistic bound for the current solution state.
18    ///
19    /// The optimistic bound is an upper bound on the score achievable
20    /// from this partial solution. It should be:
21    /// - Fast to compute
22    /// - Greater than or equal to any actual achievable score
23    ///
24    /// Returns `None` if no bound can be computed.
25    fn calculate_optimistic_bound(&self, score_director: &D) -> Option<S::Score>;
26
27    /// Calculates the pessimistic bound for the current solution state.
28    ///
29    /// The pessimistic bound is a lower bound on the score achievable
30    /// from this partial solution. This is less commonly used but can
31    /// help with certain heuristics.
32    ///
33    /// Returns `None` if no bound can be computed.
34    fn calculate_pessimistic_bound(&self, score_director: &D) -> Option<S::Score> {
35        // Default: no pessimistic bound
36        let _ = score_director;
37        None
38    }
39}
40
41/// A simple bounder that uses the current score as the optimistic bound.
42///
43/// This is useful when constraint violations can only increase (get worse)
44/// as more assignments are made, which is common for most constraint problems.
45#[derive(Debug, Clone, Default)]
46pub struct SimpleScoreBounder;
47
48impl SimpleScoreBounder {
49    /// Creates a new simple score bounder.
50    pub fn new() -> Self {
51        Self
52    }
53}
54
55impl<S: PlanningSolution, D: ScoreDirector<S>> ScoreBounder<S, D> for SimpleScoreBounder {
56    fn calculate_optimistic_bound(&self, _score_director: &D) -> Option<S::Score> {
57        // The simple bounder doesn't compute bounds
58        // This effectively disables pruning
59        None
60    }
61}
62
63/// A bounder that uses a fixed offset from the current score.
64///
65/// This assumes that future assignments can at most improve the score
66/// by a fixed amount per remaining entity.
67#[derive(Clone)]
68pub struct FixedOffsetBounder<S: PlanningSolution> {
69    /// Maximum improvement per unassigned entity.
70    max_improvement_per_entity: S::Score,
71}
72
73impl<S: PlanningSolution> std::fmt::Debug for FixedOffsetBounder<S> {
74    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
75        f.debug_struct("FixedOffsetBounder").finish()
76    }
77}
78
79impl<S: PlanningSolution> FixedOffsetBounder<S> {
80    /// Creates a new fixed offset bounder.
81    pub fn new(max_improvement_per_entity: S::Score) -> Self {
82        Self {
83            max_improvement_per_entity,
84        }
85    }
86}
87
88impl<S: PlanningSolution, D: ScoreDirector<S>> ScoreBounder<S, D> for FixedOffsetBounder<S>
89where
90    S::Score: Clone + std::ops::Add<Output = S::Score> + std::ops::Mul<i32, Output = S::Score>,
91{
92    fn calculate_optimistic_bound(&self, score_director: &D) -> Option<S::Score> {
93        // Count unassigned entities
94        let total = score_director.total_entity_count()?;
95
96        // For now, we can't easily count assigned entities
97        // so we use a simple heuristic
98        let current_score = score_director.working_solution().score()?;
99
100        // Optimistic bound = current score + max_improvement * remaining_entities
101        // Since we don't know remaining entities, we assume all could improve
102        let bound = current_score + self.max_improvement_per_entity * (total as i32);
103
104        Some(bound)
105    }
106}
107
108/// Bounder type selection.
109#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
110pub enum BounderType {
111    /// No bounding (disables pruning).
112    #[default]
113    None,
114    /// Simple score bounder.
115    Simple,
116    /// Fixed offset bounder.
117    FixedOffset,
118}
119
120impl std::fmt::Display for BounderType {
121    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
122        match self {
123            BounderType::None => write!(f, "None"),
124            BounderType::Simple => write!(f, "Simple"),
125            BounderType::FixedOffset => write!(f, "FixedOffset"),
126        }
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133
134    #[test]
135    fn test_simple_bounder_returns_none() {
136        let bounder = SimpleScoreBounder::new();
137        // SimpleScoreBounder returns None by default (disables pruning)
138        // Verify Default trait works
139        assert!(format!("{:?}", bounder).contains("SimpleScoreBounder"));
140    }
141
142    #[test]
143    fn test_bounder_type_display() {
144        assert_eq!(format!("{}", BounderType::None), "None");
145        assert_eq!(format!("{}", BounderType::Simple), "Simple");
146        assert_eq!(format!("{}", BounderType::FixedOffset), "FixedOffset");
147    }
148
149    #[test]
150    fn test_bounder_type_default() {
151        assert_eq!(BounderType::default(), BounderType::None);
152    }
153}
solverforge_solver/phase/exhaustive/bounder.rs

solverforge_solver/phase/exhaustive/
bounder.rs
