use super::*;
use crate::Result;
use crate::{
constraint::RemovedReason, ATol, Evaluate, Propagate, PropagateOutcome, VariableIDSet,
};
use std::collections::BTreeMap;
fn merge_state(
expanded: &mut v1::State,
additional: v1::State,
atol: ATol,
changed: &mut bool,
) -> Result<()> {
for (var_id, value) in additional.entries {
if let Some(&existing) = expanded.entries.get(&var_id) {
if (existing - value).abs() > *atol {
return Err(crate::error!(
"Conflicting variable fixings for ID={var_id}: \
existing={existing}, new={value}"
));
}
} else {
expanded.entries.insert(var_id, value);
*changed = true;
}
}
Ok(())
}
impl Evaluate for Instance {
type Output = crate::Solution;
type SampledOutput = crate::SampleSet;
#[tracing::instrument(skip_all)]
fn evaluate(&self, state: &v1::State, atol: ATol) -> Result<Self::Output> {
let state = self
.analyze_decision_variables()
.populate(state.clone(), atol)?;
let objective = self.objective.evaluate(&state, atol)?;
let evaluated_constraints = self.constraint_collection.evaluate(&state, atol)?;
let evaluated_indicator_constraints = self
.indicator_constraint_collection
.evaluate(&state, atol)?;
let evaluated_one_hot_constraints =
self.one_hot_constraint_collection.evaluate(&state, atol)?;
let evaluated_sos1_constraints = self.sos1_constraint_collection.evaluate(&state, atol)?;
let mut decision_variables = BTreeMap::default();
for dv in self.decision_variables.values() {
let evaluated_dv = dv.evaluate(&state, atol)?;
decision_variables.insert(*evaluated_dv.id(), evaluated_dv);
}
let mut evaluated_named_functions = BTreeMap::default();
for (id, named_function) in self.named_functions.iter() {
let evaluated_named_function = named_function.evaluate(&state, atol)?;
evaluated_named_functions.insert(*id, evaluated_named_function);
}
let sense = self.sense();
let solution = unsafe {
crate::Solution::builder()
.objective(objective)
.evaluated_constraints_collection(evaluated_constraints)
.evaluated_indicator_constraints_collection(evaluated_indicator_constraints)
.evaluated_one_hot_constraints_collection(evaluated_one_hot_constraints)
.evaluated_sos1_constraints_collection(evaluated_sos1_constraints)
.evaluated_named_functions(evaluated_named_functions)
.decision_variables(decision_variables)
.variable_metadata(self.variable_metadata.clone())
.named_function_metadata(self.named_function_metadata.clone())
.sense(sense)
.build_unchecked()?
};
Ok(solution)
}
#[tracing::instrument(skip_all)]
fn evaluate_samples(
&self,
samples: &crate::Sampled<v1::State>,
atol: ATol,
) -> Result<Self::SampledOutput> {
let samples = {
let analysis = self.analyze_decision_variables();
let mut samples = samples.clone();
for state in samples.iter_mut() {
let taken = std::mem::take(state);
*state = analysis.populate(taken, atol)?;
}
samples
};
let sampled_constraints: crate::constraint_type::SampledCollection<crate::Constraint> =
self.constraint_collection
.evaluate_samples(&samples, atol)?;
let sampled_indicator_constraints: crate::constraint_type::SampledCollection<
crate::IndicatorConstraint,
> = self
.indicator_constraint_collection
.evaluate_samples(&samples, atol)?;
let sampled_one_hot_constraints: crate::constraint_type::SampledCollection<
crate::OneHotConstraint,
> = self
.one_hot_constraint_collection
.evaluate_samples(&samples, atol)?;
let sampled_sos1_constraints: crate::constraint_type::SampledCollection<
crate::Sos1Constraint,
> = self
.sos1_constraint_collection
.evaluate_samples(&samples, atol)?;
let objectives = self.objective().evaluate_samples(&samples, atol)?;
let mut decision_variables = std::collections::BTreeMap::new();
for dv in self.decision_variables.values() {
let sampled_dv = dv.evaluate_samples(&samples, atol)?;
decision_variables.insert(dv.id(), sampled_dv);
}
let mut named_functions = std::collections::BTreeMap::new();
for (id, named_function) in self.named_functions.iter() {
let sampled_named_function = named_function.evaluate_samples(&samples, atol)?;
named_functions.insert(*id, sampled_named_function);
}
Ok(crate::SampleSet::builder()
.decision_variables(decision_variables)
.variable_metadata(self.variable_metadata.clone())
.objectives(objectives)
.constraints_collection(sampled_constraints)
.indicator_constraints_collection(sampled_indicator_constraints)
.one_hot_constraints_collection(sampled_one_hot_constraints)
.sos1_constraints_collection(sampled_sos1_constraints)
.named_functions(named_functions)
.named_function_metadata(self.named_function_metadata.clone())
.sense(self.sense)
.build()?)
}
#[tracing::instrument(skip_all)]
fn partial_evaluate(&mut self, state: &v1::State, atol: ATol) -> Result<()> {
let mut working = self.clone();
let expanded_state = working.propagate_special_constraints(state, atol)?;
for (id, value) in expanded_state.entries.iter() {
let Some(dv) = working.decision_variables.get_mut(&VariableID::from(*id)) else {
return Err(crate::error!(
"Unknown decision variable (ID={id}) in state."
));
};
dv.substitute(*value, atol)?;
}
working.objective.partial_evaluate(&expanded_state, atol)?;
working
.constraint_collection
.partial_evaluate(&expanded_state, atol)?;
for named_function in working.named_functions.values_mut() {
named_function.partial_evaluate(&expanded_state, atol)?;
}
working
.decision_variable_dependency
.partial_evaluate(&expanded_state, atol)?;
*self = working;
Ok(())
}
fn required_ids(&self) -> VariableIDSet {
self.analyze_decision_variables().used().clone()
}
}
impl Instance {
fn propagate_special_constraints(
&mut self,
state: &v1::State,
atol: ATol,
) -> Result<v1::State> {
let mut expanded = state.clone();
let mut changed = true;
let propagation_reason = RemovedReason {
reason: "ommx.Instance.partial_evaluate.unit_propagation".to_string(),
parameters: Default::default(),
};
while changed {
changed = false;
let one_hots = std::mem::take(self.one_hot_constraint_collection.active_mut());
for (id, oh) in one_hots {
let (outcome, additional) = oh.propagate(&expanded, atol)?;
merge_state(&mut expanded, additional, atol, &mut changed)?;
match outcome {
PropagateOutcome::Active(oh) => {
self.one_hot_constraint_collection
.active_mut()
.insert(id, oh);
}
PropagateOutcome::Consumed(oh) => {
self.one_hot_constraint_collection
.removed_mut()
.insert(id, (oh, propagation_reason.clone()));
}
PropagateOutcome::Transformed { new, .. } => match new {},
}
}
let sos1s = std::mem::take(self.sos1_constraint_collection.active_mut());
for (id, sos1) in sos1s {
let (outcome, additional) = sos1.propagate(&expanded, atol)?;
merge_state(&mut expanded, additional, atol, &mut changed)?;
match outcome {
PropagateOutcome::Active(sos1) => {
self.sos1_constraint_collection
.active_mut()
.insert(id, sos1);
}
PropagateOutcome::Consumed(sos1) => {
self.sos1_constraint_collection
.removed_mut()
.insert(id, (sos1, propagation_reason.clone()));
}
PropagateOutcome::Transformed { new, .. } => match new {},
}
}
let indicators = std::mem::take(self.indicator_constraint_collection.active_mut());
for (id, ic) in indicators {
let (outcome, additional) = ic.propagate(&expanded, atol)?;
merge_state(&mut expanded, additional, atol, &mut changed)?;
match outcome {
PropagateOutcome::Active(ic) => {
self.indicator_constraint_collection
.active_mut()
.insert(id, ic);
}
PropagateOutcome::Consumed(ic) => {
self.indicator_constraint_collection
.removed_mut()
.insert(id, (ic, propagation_reason.clone()));
}
PropagateOutcome::Transformed {
original,
new: constraint,
} => {
let cid = self.constraint_collection.unused_id();
let mut new_metadata = self
.indicator_constraint_collection
.metadata()
.collect_for(id);
new_metadata
.provenance
.push(crate::constraint::Provenance::IndicatorConstraint(id));
self.constraint_collection
.insert_with(cid, constraint, new_metadata);
self.indicator_constraint_collection
.removed_mut()
.insert(id, (original, propagation_reason.clone()));
}
}
}
}
Ok(expanded)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::random::arbitrary_split_state;
use crate::{coeff, linear};
use ::approx::AbsDiffEq;
use proptest::prelude::*;
use std::collections::HashMap;
proptest! {
#[test]
fn test_evaluate_instance(
(instance, state) in Instance::arbitrary()
.prop_flat_map(|instance| {
let state = instance.arbitrary_state();
(Just(instance), state)
})
) {
let analysis = instance.analyze_decision_variables();
let solution = instance.evaluate(&state, ATol::default()).unwrap();
let ids: VariableIDSet = solution.state().entries.keys().map(|id| VariableID::from(*id)).collect();
prop_assert_eq!(&ids, analysis.all());
}
#[test]
fn partial_evaluate(
(mut instance, state, (u, v)) in Instance::arbitrary()
.prop_flat_map(|instance| {
let state = instance.arbitrary_state();
(Just(instance), state).prop_flat_map(|(instance, state)| {
let split = arbitrary_split_state(&state);
(Just(instance), Just(state), split)
})
})
) {
let s1 = instance.evaluate(&state, ATol::default()).unwrap();
instance.partial_evaluate(&u, ATol::default()).unwrap();
let s2 = instance.evaluate(&v, ATol::default()).unwrap();
prop_assert!(s1.state().abs_diff_eq(&s2.state(), ATol::default()));
}
}
#[test]
fn test_evaluate_named_function_with_fixed_dependent_irrelevant_variables() {
use crate::{DecisionVariable, NamedFunction, NamedFunctionID};
use maplit::btreemap;
let x1 = DecisionVariable::continuous(VariableID::from(1));
let mut x2 = DecisionVariable::continuous(VariableID::from(2));
x2.substitute(3.0, ATol::default()).unwrap(); let x3 = DecisionVariable::continuous(VariableID::from(3));
let x4 = DecisionVariable::continuous(VariableID::from(4));
let x5 = DecisionVariable::continuous(VariableID::from(5));
let decision_variables = btreemap! {
VariableID::from(1) => x1,
VariableID::from(2) => x2,
VariableID::from(3) => x3,
VariableID::from(4) => x4,
VariableID::from(5) => x5,
};
let objective = Function::from(linear!(1));
let decision_variable_dependency = crate::AcyclicAssignments::new(vec![(
VariableID::from(3),
Function::from(coeff!(2.0) * linear!(4)),
)])
.unwrap();
let named_function = NamedFunction {
id: NamedFunctionID::from(1),
function: Function::from(linear!(2) + linear!(3) + linear!(4) + linear!(5)),
};
let named_functions = btreemap! {
NamedFunctionID::from(1) => named_function,
};
let mut instance = Instance::new(
Sense::Minimize,
objective,
decision_variables,
BTreeMap::new(), )
.unwrap();
instance.decision_variable_dependency = decision_variable_dependency;
instance.named_functions = named_functions;
let analysis = instance.analyze_decision_variables();
assert!(analysis.used().contains(&VariableID::from(1)));
assert!(analysis.fixed().contains_key(&VariableID::from(2)));
assert!(analysis.dependent().contains_key(&VariableID::from(3)));
assert!(analysis.irrelevant().contains_key(&VariableID::from(4)));
assert!(analysis.irrelevant().contains_key(&VariableID::from(5)));
let state = v1::State::from(HashMap::from([(1, 1.0), (4, 2.0), (5, 10.0)]));
let solution = instance.evaluate(&state, ATol::default()).unwrap();
assert_eq!(*solution.objective(), 1.0);
let evaluated_nf = solution
.evaluated_named_functions()
.get(&NamedFunctionID::from(1))
.unwrap();
assert_eq!(evaluated_nf.evaluated_value(), 19.0);
let used_ids = evaluated_nf.used_decision_variable_ids();
assert!(used_ids.contains(&VariableID::from(2)));
assert!(used_ids.contains(&VariableID::from(3)));
assert!(used_ids.contains(&VariableID::from(4)));
assert!(used_ids.contains(&VariableID::from(5)));
assert!(!used_ids.contains(&VariableID::from(1)));
}
#[test]
fn test_partial_evaluate_one_hot_propagation() {
use crate::{DecisionVariable, OneHotConstraint, OneHotConstraintID};
use maplit::btreemap;
let decision_variables = btreemap! {
VariableID::from(1) => DecisionVariable::binary(VariableID::from(1)),
VariableID::from(2) => DecisionVariable::binary(VariableID::from(2)),
VariableID::from(3) => DecisionVariable::binary(VariableID::from(3)),
};
let objective = Function::from(linear!(1) + linear!(2) + linear!(3));
let mut instance = Instance::new(
Sense::Minimize,
objective,
decision_variables,
BTreeMap::new(),
)
.unwrap();
let oh = OneHotConstraint::new([1, 2, 3].into_iter().map(VariableID::from).collect());
instance
.one_hot_constraint_collection
.active_mut()
.insert(OneHotConstraintID::from(1), oh);
let state = v1::State::from(HashMap::from([(2, 1.0)]));
instance.partial_evaluate(&state, ATol::default()).unwrap();
assert_eq!(
instance.decision_variables[&VariableID::from(1)].substituted_value(),
Some(0.0)
);
assert_eq!(
instance.decision_variables[&VariableID::from(2)].substituted_value(),
Some(1.0)
);
assert_eq!(
instance.decision_variables[&VariableID::from(3)].substituted_value(),
Some(0.0)
);
assert!(instance.one_hot_constraint_collection.active().is_empty());
assert_eq!(instance.one_hot_constraint_collection.removed().len(), 1);
}
#[test]
fn test_partial_evaluate_one_hot_unit_propagation() {
use crate::{DecisionVariable, OneHotConstraint, OneHotConstraintID};
use maplit::btreemap;
let decision_variables = btreemap! {
VariableID::from(1) => DecisionVariable::binary(VariableID::from(1)),
VariableID::from(2) => DecisionVariable::binary(VariableID::from(2)),
VariableID::from(3) => DecisionVariable::binary(VariableID::from(3)),
};
let objective = Function::from(linear!(1) + linear!(2) + linear!(3));
let mut instance = Instance::new(
Sense::Minimize,
objective,
decision_variables,
BTreeMap::new(),
)
.unwrap();
let oh = OneHotConstraint::new([1, 2, 3].into_iter().map(VariableID::from).collect());
instance
.one_hot_constraint_collection
.active_mut()
.insert(OneHotConstraintID::from(1), oh);
let state = v1::State::from(HashMap::from([(1, 0.0), (2, 0.0)]));
instance.partial_evaluate(&state, ATol::default()).unwrap();
assert_eq!(
instance.decision_variables[&VariableID::from(3)].substituted_value(),
Some(1.0)
);
}
#[test]
fn test_partial_evaluate_cascade_one_hot_sos1() {
use crate::{
DecisionVariable, OneHotConstraint, OneHotConstraintID, Sos1Constraint,
Sos1ConstraintID,
};
use maplit::btreemap;
let decision_variables = btreemap! {
VariableID::from(1) => DecisionVariable::binary(VariableID::from(1)),
VariableID::from(2) => DecisionVariable::binary(VariableID::from(2)),
VariableID::from(3) => DecisionVariable::continuous(VariableID::from(3)),
};
let objective = Function::from(linear!(1) + linear!(2) + linear!(3));
let mut instance = Instance::new(
Sense::Minimize,
objective,
decision_variables,
BTreeMap::new(),
)
.unwrap();
let oh = OneHotConstraint::new([1, 2].into_iter().map(VariableID::from).collect());
instance
.one_hot_constraint_collection
.active_mut()
.insert(OneHotConstraintID::from(1), oh);
let sos1 = Sos1Constraint::new([2, 3].into_iter().map(VariableID::from).collect());
instance
.sos1_constraint_collection
.active_mut()
.insert(Sos1ConstraintID::from(1), sos1);
let state = v1::State::from(HashMap::from([(1, 1.0)]));
instance.partial_evaluate(&state, ATol::default()).unwrap();
assert_eq!(
instance.decision_variables[&VariableID::from(2)].substituted_value(),
Some(0.0)
);
assert!(instance.one_hot_constraint_collection.active().is_empty());
let sos1_active = instance.sos1_constraint_collection.active();
assert_eq!(sos1_active.len(), 1);
let remaining_sos1 = sos1_active.values().next().unwrap();
assert_eq!(remaining_sos1.variables.len(), 1);
assert!(remaining_sos1.variables.contains(&VariableID::from(3)));
}
#[test]
fn test_partial_evaluate_indicator_promotion() {
use crate::{constraint::Equality, DecisionVariable, IndicatorConstraintID};
use maplit::btreemap;
let decision_variables = btreemap! {
VariableID::from(1) => DecisionVariable::continuous(VariableID::from(1)),
VariableID::from(2) => DecisionVariable::continuous(VariableID::from(2)),
VariableID::from(10) => DecisionVariable::binary(VariableID::from(10)),
};
let objective = Function::from(linear!(1) + linear!(2));
let mut indicator_constraints = BTreeMap::new();
indicator_constraints.insert(
IndicatorConstraintID::from(100),
crate::IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
Function::from(linear!(1) + linear!(2) + coeff!(-5.0)),
),
);
let instance = Instance::builder()
.sense(Sense::Minimize)
.objective(objective)
.decision_variables(decision_variables)
.constraints(BTreeMap::new())
.indicator_constraints(indicator_constraints)
.build()
.unwrap();
let mut instance = instance;
let state = v1::State::from(HashMap::from([(10, 1.0)]));
instance.partial_evaluate(&state, ATol::default()).unwrap();
assert!(instance.indicator_constraint_collection.active().is_empty());
assert_eq!(instance.indicator_constraint_collection.removed().len(), 1);
assert_eq!(instance.constraint_collection.active().len(), 1);
let (cid, _promoted) = instance
.constraint_collection
.active()
.iter()
.next()
.unwrap();
assert_eq!(
instance.constraint_collection.metadata().provenance(*cid),
&[crate::constraint::Provenance::IndicatorConstraint(
IndicatorConstraintID::from(100)
)]
);
}
#[test]
fn test_partial_evaluate_indicator_removed() {
use crate::{constraint::Equality, DecisionVariable, IndicatorConstraintID};
use maplit::btreemap;
let decision_variables = btreemap! {
VariableID::from(1) => DecisionVariable::continuous(VariableID::from(1)),
VariableID::from(10) => DecisionVariable::binary(VariableID::from(10)),
};
let objective = Function::from(linear!(1));
let mut indicator_constraints = BTreeMap::new();
indicator_constraints.insert(
IndicatorConstraintID::from(1),
crate::IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
Function::from(linear!(1) + coeff!(-5.0)),
),
);
let mut instance = Instance::builder()
.sense(Sense::Minimize)
.objective(objective)
.decision_variables(decision_variables)
.constraints(BTreeMap::new())
.indicator_constraints(indicator_constraints)
.build()
.unwrap();
let state = v1::State::from(HashMap::from([(10, 0.0)]));
instance.partial_evaluate(&state, ATol::default()).unwrap();
assert!(instance.indicator_constraint_collection.active().is_empty());
assert_eq!(instance.indicator_constraint_collection.removed().len(), 1);
assert!(instance.constraint_collection.active().is_empty());
}
}