solverforge_solver/phase/exhaustive/
bounder.rs

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

solverforge_solver/phase/exhaustive/
bounder.rs
