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

solverforge_solver/phase/exhaustive/
bounder.rs
