csp-solver 0.2.0

Generic constraint satisfaction problem solver with backtracking, AC-3 constraint propagation, and ordering heuristics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

//! Cost-evaluation vocabulary for branch-and-bound optimization.
//!
//! The branch-and-bound *search* now lives in the unified kernel
//! ([`crate::solver::search::branch_and_bound`]); this module owns only the
//! cost abstraction the optimizer plugs in — [`DomainCostEval`] and its two
//! implementors ([`ZeroCost`], [`CostDomainEval`]).
//!
//! # Deferred extensions (Phase 2 design decisions)
//!
//! **`TieredCostEval` / lazy cost evaluation** — deferred because the
//! [`crate::domain::CostDomain::min_cost`] incremental `Cell` cache covers the
//! immediate bottleneck: the optimizer's optimistic bound was calling
//! `min_cost()` O(domain) per node, and the cache amortizes that to O(1). A
//! tiered evaluator (cheap proxy lower bound + expensive actual cost with
//! memoization) only pays its API cost when a second consumer with a genuinely
//! non-trivial cost function appears. [`DomainCostEval`] is the extension point
//! — implement a new evaluator type, no solver-core changes needed.
//!
//! **`solve_with_warm_start`** — deferred because no consumer currently demands
//! incremental re-solving (accepting a previous solution as the initial
//! incumbent for tighter pruning from node zero). Land it when the first
//! incremental consumer (e.g. a playground animation scrubber) appears.

use crate::domain::Domain;

/// Cost evaluator for domains. Passed into the optimizer so the same search
/// code works for both `CostDomain` and plain `Domain` (zero cost).
pub trait DomainCostEval<D: Domain> {
    /// Cost of assigning `val` to the variable whose current domain is `domain`.
    fn cost(&self, domain: &D, val: &D::Value) -> f64;
    /// Lower bound on the minimum cost achievable from `domain`.
    fn min_cost(&self, domain: &D) -> f64;
    /// Upper bound on the maximum cost achievable from `domain`.
    fn max_cost(&self, domain: &D) -> f64;
}

/// No-op evaluator: all costs are zero. Used when `D` doesn't implement `CostDomain`.
pub struct ZeroCost;

impl<D: Domain> DomainCostEval<D> for ZeroCost {
    #[inline]
    fn cost(&self, _domain: &D, _val: &D::Value) -> f64 {
        0.0
    }
    #[inline]
    fn min_cost(&self, _domain: &D) -> f64 {
        0.0
    }
    #[inline]
    fn max_cost(&self, _domain: &D) -> f64 {
        0.0
    }
}

/// Evaluator that delegates to `CostDomain` methods.
pub struct CostDomainEval;

impl<D: crate::domain::CostDomain> DomainCostEval<D> for CostDomainEval {
    #[inline]
    fn cost(&self, domain: &D, val: &D::Value) -> f64 {
        domain.cost(val)
    }
    #[inline]
    fn min_cost(&self, domain: &D) -> f64 {
        domain.min_cost()
    }
    #[inline]
    fn max_cost(&self, domain: &D) -> f64 {
        domain
            .values()
            .into_iter()
            .map(|v| domain.cost(&v))
            .fold(f64::NEG_INFINITY, f64::max)
    }
}