csp_solver/solver/
optimize.rs

1//! Cost-evaluation vocabulary for branch-and-bound optimization.
2//!
3//! The branch-and-bound *search* now lives in the unified kernel
4//! ([`crate::solver::search::branch_and_bound`]); this module owns only the
5//! cost abstraction the optimizer plugs in — [`DomainCostEval`] and its two
6//! implementors ([`ZeroCost`], [`CostDomainEval`]).
7
8use crate::domain::Domain;
9
10/// Cost evaluator for domains. Passed into the optimizer so the same search
11/// code works for both `CostDomain` and plain `Domain` (zero cost).
12pub trait DomainCostEval<D: Domain> {
13    /// Cost of assigning `val` to the variable whose current domain is `domain`.
14    fn cost(&self, domain: &D, val: &D::Value) -> f64;
15    /// Lower bound on the minimum cost achievable from `domain`.
16    fn min_cost(&self, domain: &D) -> f64;
17    /// Upper bound on the maximum cost achievable from `domain`.
18    fn max_cost(&self, domain: &D) -> f64;
19}
20
21/// No-op evaluator: all costs are zero. Used when `D` doesn't implement `CostDomain`.
22pub(crate) struct ZeroCost;
23
24impl<D: Domain> DomainCostEval<D> for ZeroCost {
25    #[inline]
26    fn cost(&self, _domain: &D, _val: &D::Value) -> f64 {
27        0.0
28    }
29    #[inline]
30    fn min_cost(&self, _domain: &D) -> f64 {
31        0.0
32    }
33    #[inline]
34    fn max_cost(&self, _domain: &D) -> f64 {
35        0.0
36    }
37}
38
39/// Evaluator that delegates to `CostDomain` methods.
40pub(crate) struct CostDomainEval;
41
42impl<D: crate::domain::CostDomain> DomainCostEval<D> for CostDomainEval {
43    #[inline]
44    fn cost(&self, domain: &D, val: &D::Value) -> f64 {
45        domain.cost(val)
46    }
47    #[inline]
48    fn min_cost(&self, domain: &D) -> f64 {
49        domain.min_cost()
50    }
51    #[inline]
52    fn max_cost(&self, domain: &D) -> f64 {
53        domain
54            .values()
55            .into_iter()
56            .map(|v| domain.cost(&v))
57            .fold(f64::NEG_INFINITY, f64::max)
58    }
59}
csp_solver/solver/optimize.rs

csp_solver/solver/
optimize.rs
