use rustc_hash::FxHashSet;
use std::collections::HashMap;
use std::sync::{Arc, RwLock};
use crate::constraints::{
AllDifferent, Among, AtLeast, Constraint, ConstraintShapeKey, Gcc, NotEquals, Regular, Sum,
};
use crate::mdd::compiler::enforce_precedence_order;
use crate::mdd::heuristics::{
CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
};
use crate::mdd::{Compiler, Mdd};
use crate::modelling::{ConstraintIndex, Problem, VariableIndex};
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) struct ConstraintCompileKey {
shape: ConstraintShapeKey,
domain: Vec<isize>,
max_width: usize,
}
pub(crate) fn nominal_domain(domain_size: usize) -> Vec<isize> {
(0..domain_size as isize).collect()
}
fn constraint_shape_key(
problem: &Problem,
constraint: ConstraintIndex,
domain: &[isize],
max_width: usize,
) -> ConstraintCompileKey {
ConstraintCompileKey {
shape: problem[constraint].structural_key(problem),
domain: domain.to_vec(),
max_width,
}
}
fn instantiate_constraint(
shape: &ConstraintShapeKey,
synthetic_variables: Vec<VariableIndex>,
synthetic_problem: &Problem,
) -> Box<dyn Constraint + Send + Sync> {
match shape {
ConstraintShapeKey::AllDifferent { arity: _ } => {
Box::new(AllDifferent::new(synthetic_variables, synthetic_problem))
}
ConstraintShapeKey::NotEquals => {
if synthetic_variables.len() != 2 {
panic!(
"NotEquals shape key must instantiate over exactly 2 variables, got {}",
synthetic_variables.len()
);
}
Box::new(NotEquals::new(
synthetic_variables[0],
synthetic_variables[1],
synthetic_problem,
))
}
ConstraintShapeKey::Among {
arity: _,
values,
lb,
ub,
} => Box::new(Among::new(
synthetic_variables,
FxHashSet::from_iter(values.iter().copied()),
*lb,
*ub,
)),
ConstraintShapeKey::AtLeast {
arity: _,
values,
lb,
} => Box::new(AtLeast::new(
synthetic_variables,
FxHashSet::from_iter(values.iter().copied()),
*lb,
)),
ConstraintShapeKey::Gcc { arity: _, bounds } => {
Box::new(Gcc::new(synthetic_variables, bounds.clone()))
}
ConstraintShapeKey::Regular {
arity: _,
transitions,
initial_state,
accepting_states,
} => Box::new(Regular::new(
synthetic_variables,
transitions.clone(),
*initial_state,
FxHashSet::from_iter(accepting_states.iter().copied()),
synthetic_problem,
)),
ConstraintShapeKey::Sum { arity: _, target } => {
Box::new(Sum::new(synthetic_variables, *target, synthetic_problem))
}
}
}
fn compile_template(key: &ConstraintCompileKey) -> Mdd {
let mut synthetic_problem = Problem::default();
let synthetic_vars: Vec<VariableIndex> = (0..key.shape.arity())
.map(|_| synthetic_problem.add_variable(key.domain.clone()))
.collect();
let constraint = instantiate_constraint(&key.shape, synthetic_vars, &synthetic_problem);
synthetic_problem.add_constraint_boxed(constraint);
let synthetic_problem = Arc::new(synthetic_problem);
let constraints: Vec<ConstraintIndex> = synthetic_problem.iter_constraints().collect();
let mut compiler = Compiler::new(
Arc::clone(&synthetic_problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::StateSimilarity,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
compiler.refine(key.max_width);
compiler.into_mdd()
}
#[derive(Default)]
pub struct MddArena {
cache: RwLock<HashMap<ConstraintCompileKey, Arc<Mdd>>>,
}
impl MddArena {
pub fn new() -> Self {
Self::default()
}
pub fn len(&self) -> usize {
self.cache.read().expect("MddArena lock poisoned").len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
fn structure_for(&self, key: &ConstraintCompileKey) -> Arc<Mdd> {
if let Some(structure) = self.cache.read().expect("MddArena lock poisoned").get(key) {
return Arc::clone(structure);
}
let structure = Arc::new(compile_template(key));
let mut cache = self.cache.write().expect("MddArena lock poisoned");
Arc::clone(cache.entry(key.clone()).or_insert(structure))
}
}
pub struct CompiledConstraint {
pub structure: Arc<Mdd>,
pub order: Vec<VariableIndex>,
}
impl CompiledConstraint {
pub(crate) fn decision_at_layer(&self, layer: usize) -> VariableIndex {
self.order[layer]
}
}
impl CompiledConstraint {
#[cfg(test)]
pub(crate) fn from_mdd(mdd: Mdd) -> Self {
let order = (0..mdd.number_decisions())
.map(|layer| mdd.decision_at_layer(layer))
.collect();
Self {
structure: Arc::new(mdd),
order,
}
}
pub(crate) fn number_decisions(&self) -> usize {
self.order.len()
}
}
impl std::ops::Deref for CompiledConstraint {
type Target = Mdd;
fn deref(&self) -> &Mdd {
&self.structure
}
}
fn compute_constraint_order(
problem: &Problem,
constraint: ConstraintIndex,
ordering: &OrderingHeuristic,
) -> Vec<VariableIndex> {
let scope: Vec<VariableIndex> = problem[constraint].iter_scope().collect();
let owned: Vec<Box<dyn Constraint>> = vec![problem[constraint].clone()];
let order = ordering.get_order(problem, &scope);
enforce_precedence_order(order, &owned)
}
pub(crate) fn compile_constraint(
arena: &MddArena,
problem: &Problem,
constraint: ConstraintIndex,
ordering: &OrderingHeuristic,
domain: &[isize],
max_width: usize,
) -> CompiledConstraint {
let key = constraint_shape_key(problem, constraint, domain, max_width);
let structure = arena.structure_for(&key);
let order = compute_constraint_order(problem, constraint, ordering);
debug_assert!(
structure.is_unsat() || order.len() + 1 == structure.number_layers(),
"a real constraint's branching order must have exactly one fewer entry than its \
arena-shared structure's layer count (the structure has one extra, sink, layer) -- a \
mismatch here means the constraint's real scope doesn't actually match the shape key it \
was compiled/looked-up under"
);
CompiledConstraint { structure, order }
}
#[derive(Clone, Debug)]
pub struct MddCompilationConfig {
pub ordering: OrderingHeuristic,
#[allow(dead_code)]
pub merge: MergeHeuristic,
#[allow(dead_code)]
pub select: SelectHeuristic,
pub max_width: usize,
}
impl Default for MddCompilationConfig {
fn default() -> Self {
Self {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::default(),
select: SelectHeuristic::Greedy,
max_width: usize::MAX,
}
}
}
pub fn compile_constraints(
problem: &Problem,
arena: &MddArena,
config: &MddCompilationConfig,
domain_size: usize,
) -> Vec<CompiledConstraint> {
let domain = nominal_domain(domain_size);
problem
.iter_constraints()
.map(|c| {
let label = problem[c].name();
for variable in problem[c].iter_scope() {
for value in problem[variable].iter_domain() {
assert!(
value >= 0 && (value as usize) < domain_size,
"constraint `{}`: domain value {} out of the nominal [0, {}) range",
label,
value,
domain_size,
);
}
}
let compiled = compile_constraint(
arena,
problem,
c,
&config.ordering,
&domain,
config.max_width,
);
if compiled.structure.is_unsat() {
log::warn!(
"MDD constraint `{}`'s shape is unconditionally unsatisfiable",
label,
);
}
compiled
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::{all_different, among, at_least, gcc, not_equals, regular, sum};
use crate::mdd::NodeIndex;
use crate::modelling::ValueIndex;
fn accepts(compiled: &CompiledConstraint, tuple: &[isize]) -> bool {
if compiled.is_unsat() {
return false;
}
let mut node = compiled.root();
for layer in 0..compiled.order.len() {
let value = ValueIndex(tuple[compiled.order[layer].0] as usize);
let next = compiled[node]
.iter_children()
.map(|edge| &compiled[edge])
.find(|edge| edge.is_active() && edge.assignment() == value)
.map(|edge| edge.to());
match next {
Some(to) => node = to,
None => return false,
}
}
node == compiled.sink() && !compiled.is_unsat()
}
fn all_tuples(variables: usize, domain: isize) -> Vec<Vec<isize>> {
let mut tuples = vec![vec![]];
for _ in 0..variables {
tuples = tuples
.into_iter()
.flat_map(|t| {
(0..domain).map(move |v| {
let mut t = t.clone();
t.push(v);
t
})
})
.collect();
}
tuples
}
fn one_of_each_constraint() -> (Problem, Vec<ConstraintIndex>) {
let mut problem = Problem::default();
let v = problem.add_variables(4, (0..3isize).collect());
for other in 0..3 {
not_equals(&mut problem, v[3], v[other]);
}
let constraints = vec![
all_different(&mut problem, vec![v[0], v[1], v[2]]),
not_equals(&mut problem, v[1], v[3]),
among(&mut problem, v.clone(), vec![0, 1], 1, 2),
at_least(&mut problem, v.clone(), vec![2], 2),
gcc(&mut problem, v.clone(), vec![(0, 1, 2), (2, 0, 1)]),
sum(&mut problem, v.clone(), 5),
regular(
&mut problem,
v.clone(),
vec![
vec![Some(1), Some(2), Some(3)],
vec![None, Some(2), Some(3)],
vec![Some(1), None, Some(3)],
vec![Some(1), Some(2), None],
],
0,
vec![1, 2, 3],
),
];
(problem, constraints)
}
#[test]
fn an_exact_structure_accepts_exactly_the_satisfying_tuples() {
let (problem, constraints) = one_of_each_constraint();
let arena = MddArena::new();
for constraint in constraints {
let compiled = compile_constraint(
&arena,
&problem,
constraint,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
for tuple in all_tuples(4, 3) {
assert_eq!(
accepts(&compiled, &tuple),
problem[constraint].is_satisfied(&tuple),
"{} on {tuple:?}",
problem[constraint].name()
);
}
}
}
#[test]
fn a_width_limited_structure_accepts_every_satisfying_tuple() {
let (problem, constraints) = one_of_each_constraint();
let arena = MddArena::new();
for constraint in constraints {
for width in [1, 2, 3] {
let compiled = compile_constraint(
&arena,
&problem,
constraint,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
width,
);
for tuple in all_tuples(4, 3) {
if problem[constraint].is_satisfied(&tuple) {
assert!(
accepts(&compiled, &tuple),
"{} at width {width} lost {tuple:?}",
problem[constraint].name()
);
}
}
}
}
}
#[test]
fn the_order_lists_the_scope_of_the_constraint_once() {
let (problem, constraints) = one_of_each_constraint();
let arena = MddArena::new();
let mut reordered = 0;
for constraint in constraints {
let compiled = compile_constraint(
&arena,
&problem,
constraint,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
let declared: Vec<_> = problem[constraint].iter_scope().collect();
reordered += usize::from(compiled.order != declared);
let mut order = compiled.order.clone();
order.sort();
let mut scope: Vec<_> = problem[constraint].iter_scope().collect();
scope.sort();
assert_eq!(order, scope, "{}", problem[constraint].name());
assert_eq!(compiled.number_layers(), scope.len() + 1);
assert_eq!(compiled.root(), NodeIndex(0, 0));
}
assert!(reordered > 0);
}
#[test]
fn the_width_and_the_domain_are_part_of_the_key() {
let mut problem = Problem::default();
let v = problem.add_variables(3, (0..3isize).collect());
let c = all_different(&mut problem, v);
let arena = MddArena::new();
let compile = |domain_size: usize, max_width| {
compile_constraint(
&arena,
&problem,
c,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(domain_size),
max_width,
)
};
let exact = compile(3, usize::MAX);
let again = compile(3, usize::MAX);
let narrow = compile(3, 2);
let wider_domain = compile(4, usize::MAX);
assert!(Arc::ptr_eq(&exact.structure, &again.structure));
assert!(!Arc::ptr_eq(&exact.structure, &narrow.structure));
assert!(!Arc::ptr_eq(&exact.structure, &wider_domain.structure));
assert_eq!(arena.len(), 3);
assert!(!arena.is_empty());
assert!(MddArena::new().is_empty());
}
#[test]
fn threads_asking_for_the_same_shape_share_one_structure() {
let mut problem = Problem::default();
let v = problem.add_variables(5, (0..5isize).collect());
let c = all_different(&mut problem, v);
let arena = MddArena::new();
let structures: Vec<_> = std::thread::scope(|scope| {
let handles: Vec<_> = (0..8)
.map(|_| {
scope.spawn(|| {
compile_constraint(
&arena,
&problem,
c,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(5),
usize::MAX,
)
.structure
})
})
.collect();
handles.into_iter().map(|h| h.join().unwrap()).collect()
});
assert_eq!(arena.len(), 1);
assert!(
structures
.windows(2)
.all(|pair| Arc::ptr_eq(&pair[0], &pair[1]))
);
}
#[test]
fn structurally_identical_constraints_from_different_scopes_share_one_arena_entry() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, (0..3isize).collect());
let g1 = gcc(
&mut problem,
vec![vars[0], vars[1]],
vec![(0, 0, 1), (1, 0, 1)],
);
let g2 = gcc(
&mut problem,
vec![vars[2], vars[3]],
vec![(0, 0, 1), (1, 0, 1)],
);
let problem = Arc::new(problem);
let arena = MddArena::new();
let a = compile_constraint(
&arena,
&problem,
g1,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
let b = compile_constraint(
&arena,
&problem,
g2,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
assert!(Arc::ptr_eq(&a.structure, &b.structure));
assert_eq!(arena.len(), 1);
assert_ne!(
a.order, b.order,
"each constraint must keep its own real scope"
);
}
#[test]
fn differently_shaped_constraints_do_not_share() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, (0..3isize).collect());
let g1 = gcc(&mut problem, vec![vars[0], vars[1]], vec![(0, 0, 1)]);
let g2 = gcc(&mut problem, vec![vars[2], vars[3]], vec![(0, 1, 2)]);
let problem = Arc::new(problem);
let arena = MddArena::new();
let a = compile_constraint(
&arena,
&problem,
g1,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
let b = compile_constraint(
&arena,
&problem,
g2,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
assert!(!Arc::ptr_eq(&a.structure, &b.structure));
assert_eq!(arena.len(), 2);
}
#[test]
fn all_different_constraints_of_different_arity_do_not_share() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, (0..4isize).collect());
let g3 = all_different(&mut problem, vec![vars[0], vars[1], vars[2]]);
let g4 = all_different(&mut problem, vec![vars[0], vars[1], vars[2], vars[3]]);
let problem = Arc::new(problem);
let arena = MddArena::new();
let a = compile_constraint(
&arena,
&problem,
g3,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(4),
usize::MAX,
);
let b = compile_constraint(
&arena,
&problem,
g4,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(4),
usize::MAX,
);
assert!(!Arc::ptr_eq(&a.structure, &b.structure));
assert_eq!(arena.len(), 2);
assert_eq!(a.order.len(), 3);
assert_eq!(b.order.len(), 4);
}
#[test]
fn symmetric_graph_coloring_edges_with_different_degree_endpoints_still_dedup() {
let mut problem = Problem::default();
let colours: Vec<isize> = (0..3).collect();
let vars = problem.add_variables(6, colours);
let e1 = not_equals(&mut problem, vars[0], vars[1]);
for i in 2..6 {
not_equals(&mut problem, vars[0], vars[i]);
}
let e2 = not_equals(&mut problem, vars[4], vars[5]);
let problem = Arc::new(problem);
let arena = MddArena::new();
let a = compile_constraint(
&arena,
&problem,
e1,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
let b = compile_constraint(
&arena,
&problem,
e2,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
assert!(
Arc::ptr_eq(&a.structure, &b.structure),
"symmetric NotEquals edges with different-degree endpoints must still dedup"
);
assert_eq!(arena.len(), 1);
}
}