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//!
8//! # Deferred extensions (Phase 2 design decisions)
9//!
10//! **`TieredCostEval` / lazy cost evaluation** — deferred because the
11//! [`crate::domain::CostDomain::min_cost`] incremental `Cell` cache covers the
12//! immediate bottleneck: the optimizer's optimistic bound was calling
13//! `min_cost()` O(domain) per node, and the cache amortizes that to O(1). A
14//! tiered evaluator (cheap proxy lower bound + expensive actual cost with
15//! memoization) only pays its API cost when a second consumer with a genuinely
16//! non-trivial cost function appears. [`DomainCostEval`] is the extension point
17//! — implement a new evaluator type, no solver-core changes needed.
18//!
19//! **`solve_with_warm_start`** — deferred because no consumer currently demands
20//! incremental re-solving (accepting a previous solution as the initial
21//! incumbent for tighter pruning from node zero). Land it when the first
22//! incremental consumer (e.g. a playground animation scrubber) appears.
23
24use crate::domain::Domain;
25
26/// Cost evaluator for domains. Passed into the optimizer so the same search
27/// code works for both `CostDomain` and plain `Domain` (zero cost).
28pub trait DomainCostEval<D: Domain> {
29    /// Cost of assigning `val` to the variable whose current domain is `domain`.
30    fn cost(&self, domain: &D, val: &D::Value) -> f64;
31    /// Lower bound on the minimum cost achievable from `domain`.
32    fn min_cost(&self, domain: &D) -> f64;
33    /// Upper bound on the maximum cost achievable from `domain`.
34    fn max_cost(&self, domain: &D) -> f64;
35}
36
37/// No-op evaluator: all costs are zero. Used when `D` doesn't implement `CostDomain`.
38pub struct ZeroCost;
39
40impl<D: Domain> DomainCostEval<D> for ZeroCost {
41    #[inline]
42    fn cost(&self, _domain: &D, _val: &D::Value) -> f64 {
43        0.0
44    }
45    #[inline]
46    fn min_cost(&self, _domain: &D) -> f64 {
47        0.0
48    }
49    #[inline]
50    fn max_cost(&self, _domain: &D) -> f64 {
51        0.0
52    }
53}
54
55/// Evaluator that delegates to `CostDomain` methods.
56pub struct CostDomainEval;
57
58impl<D: crate::domain::CostDomain> DomainCostEval<D> for CostDomainEval {
59    #[inline]
60    fn cost(&self, domain: &D, val: &D::Value) -> f64 {
61        domain.cost(val)
62    }
63    #[inline]
64    fn min_cost(&self, domain: &D) -> f64 {
65        domain.min_cost()
66    }
67    #[inline]
68    fn max_cost(&self, domain: &D) -> f64 {
69        domain
70            .values()
71            .into_iter()
72            .map(|v| domain.cost(&v))
73            .fold(f64::NEG_INFINITY, f64::max)
74    }
75}
csp_solver/solver/optimize.rs

csp_solver/solver/
optimize.rs
