unifier 0.5.0

Constraint satisfaction / optimization (CSP/COP) modeling and solver framework for Rust, built on pathwise
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

//! Temporal precedence constraint between scheduling intervals.
//!
//! Enforces `end(A) + min_delay <= start(B)`.
//!
//! Structurally equivalent to `end(A) <= start(B) + (-min_delay)`, so this is implemented as a
//! thin wrapper around [`LessThanOrEqual`].
//!
//! Reference:
//! - Baptiste, P., Le Pape, C., & Nuijten, W. (2001). *Constraint-Based Scheduling*. Springer.

use crate::constraint::{Assignment, Constraint, Explanation, LessThanOrEqual, PropagationResult};
use crate::model::domain::TrailedDomains;
use crate::model::interval::Interval;
use crate::model::variable::VariableId;
use std::collections::HashMap;

/// Precedence constraint enforcing `end(A) + min_delay <= start(B)`.
#[derive(Debug, Clone)]
pub struct Precedence {
    inner: LessThanOrEqual,
}

impl Precedence {
    /// Creates a precedence constraint between `interval_a` and `interval_b`.
    ///
    /// # Complexity
    /// Time & Space: O(1).
    pub fn new(interval_a: &Interval, interval_b: &Interval, min_delay: i64) -> Self {
        Self {
            inner: LessThanOrEqual::new(interval_a.end(), interval_b.start(), -min_delay),
        }
    }
}

impl Constraint for Precedence {
    fn name(&self) -> &str {
        "Precedence"
    }

    fn scope(&self) -> &[VariableId] {
        self.inner.scope()
    }

    fn is_satisfied(&self, assignment: &HashMap<VariableId, i64>) -> bool {
        self.inner.is_satisfied(assignment)
    }

    fn explain(&self, assignment: &Assignment) -> Option<Explanation> {
        if self.is_satisfied(assignment) {
            return None;
        }
        let scope = self.scope();
        let end = assignment[&scope[0]];
        let start = assignment[&scope[1]];
        Some(Explanation {
            constraint_name: "Precedence",
            involved: scope.to_vec(),
            message: format!(
                "Predecessor end {end} is later than the allowed successor start {start}"
            ),
        })
    }

    fn propagate(&self, domains: &mut TrailedDomains) -> PropagationResult {
        self.inner.propagate(domains)
    }
}