use super::Instance;
use crate::{
constraint::{ConstraintContext, ConstraintID, Equality, Provenance, RemovedReason},
indicator_constraint::IndicatorConstraintID,
Bounds, Coefficient, Constraint, Evaluate, Kind, Linear, LinearMonomial,
};
use anyhow::{bail, Context, Result};
use std::collections::BTreeMap;
#[derive(Debug, Clone)]
struct IndicatorPlan {
generated_constraints: Vec<Constraint>,
}
impl Instance {
#[cfg_attr(doc, katexit::katexit)]
pub fn convert_indicator_to_constraint(
&mut self,
id: IndicatorConstraintID,
) -> Result<Vec<ConstraintID>> {
let plan = self.plan_indicator_conversion(id)?;
self.apply_indicator_conversion(id, plan)
}
pub fn convert_all_indicators_to_constraints(
&mut self,
) -> Result<BTreeMap<IndicatorConstraintID, Vec<ConstraintID>>> {
let ids: Vec<_> = self
.indicator_constraint_collection
.active()
.keys()
.copied()
.collect();
let mut all_plans: Vec<(IndicatorConstraintID, IndicatorPlan)> =
Vec::with_capacity(ids.len());
for id in ids {
let plan = self.plan_indicator_conversion(id)?;
all_plans.push((id, plan));
}
let mut result = BTreeMap::new();
for (id, plan) in all_plans {
result.insert(id, self.apply_indicator_conversion(id, plan)?);
}
Ok(result)
}
fn plan_indicator_conversion(&self, id: IndicatorConstraintID) -> Result<IndicatorPlan> {
let ic = self
.indicator_constraint_collection
.active()
.get(&id)
.with_context(|| format!("Indicator constraint with ID {id:?} not found"))?;
let function = ic.function().clone();
let equality = ic.equality;
let indicator_variable = ic.indicator_variable;
for var_id in function.required_ids() {
let dv = self.decision_variables.get(&var_id).with_context(|| {
format!(
"Decision variable {var_id:?} referenced by indicator constraint {id:?} not found"
)
})?;
if matches!(dv.kind(), Kind::SemiInteger | Kind::SemiContinuous) {
bail!(
"Cannot convert indicator constraint {id:?} with Big-M: variable {var_id:?} has kind {:?}; semi-continuous / semi-integer variables are not supported",
dv.kind()
);
}
}
let bounds: Bounds = self
.decision_variables
.iter()
.map(|(v, dv)| (*v, dv.bound()))
.collect();
let fbound = function.evaluate_bound(&bounds);
let upper_val = fbound.upper();
if !upper_val.is_finite() {
bail!(
"Cannot convert indicator constraint {id:?} with Big-M: function has non-finite upper bound {upper_val}"
);
}
let upper_big_m = if upper_val > 0.0 {
Some(Coefficient::try_from(upper_val).expect("finite positive upper bound"))
} else {
None
};
let lower_big_m = match equality {
Equality::EqualToZero => {
let lower_val = fbound.lower();
if !lower_val.is_finite() {
bail!(
"Cannot convert indicator constraint {id:?} with Big-M: function has non-finite lower bound {lower_val}"
);
}
if lower_val < 0.0 {
Some(Coefficient::try_from(lower_val).expect("finite negative lower bound"))
} else {
None
}
}
Equality::LessThanOrEqualToZero => None,
};
let mut generated_constraints = Vec::new();
if let Some(u) = upper_big_m {
let f = (function.clone()
+ Linear::single_term(LinearMonomial::Variable(indicator_variable), u))?;
let f = (f + Linear::from(-u))?;
generated_constraints.push(Constraint::less_than_or_equal_to_zero(f));
}
if let Some(l) = lower_big_m {
let neg_l = -l;
let f = (-function.clone()
+ Linear::single_term(LinearMonomial::Variable(indicator_variable), neg_l))?;
let f = (f + Linear::from(l))?;
generated_constraints.push(Constraint::less_than_or_equal_to_zero(f));
}
Ok(IndicatorPlan {
generated_constraints,
})
}
fn apply_indicator_conversion(
&mut self,
id: IndicatorConstraintID,
plan: IndicatorPlan,
) -> Result<Vec<ConstraintID>> {
let mut new_ids: Vec<ConstraintID> = Vec::with_capacity(plan.generated_constraints.len());
for constraint in plan.generated_constraints {
let new_id = self.insert_indicator_generated_constraint(id, constraint);
new_ids.push(new_id);
}
let mut parameters = fnv::FnvHashMap::default();
let constraint_ids_str = new_ids
.iter()
.map(|id| id.into_inner().to_string())
.collect::<Vec<_>>()
.join(",");
parameters.insert("constraint_ids".to_string(), constraint_ids_str);
self.indicator_constraint_collection
.relax(
id,
RemovedReason {
reason: "ommx.Instance.convert_indicator_to_constraint".to_string(),
parameters,
},
)
.expect(
"indicator id was present when the plan was built and hasn't been touched since",
);
Ok(new_ids)
}
fn insert_indicator_generated_constraint(
&mut self,
indicator_id: IndicatorConstraintID,
constraint: Constraint,
) -> ConstraintID {
let new_id = self.constraint_collection.unused_id();
let context = ConstraintContext {
provenance: vec![Provenance::IndicatorConstraint(indicator_id)],
..Default::default()
};
self.constraint_collection
.insert_active_with_context(new_id, constraint, context)
.expect("new_id was allocated from this collection");
new_id
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
coeff, indicator_constraint::IndicatorConstraint, linear, Bound, DecisionVariable,
Function, Kind, Sense, VariableID,
};
use ::approx::assert_abs_diff_eq;
use maplit::btreemap;
use std::collections::BTreeMap;
fn single_indicator_instance(
x_bound: Bound,
equality: Equality,
function: Function,
) -> Instance {
let x = DecisionVariable::new(Kind::Continuous, x_bound, crate::ATol::default()).unwrap();
let y = DecisionVariable::binary();
let ic = IndicatorConstraint::new(VariableID::from(10), equality, function);
Instance::builder()
.sense(Sense::Minimize)
.objective(Function::from(linear!(1)))
.decision_variables(btreemap! {
VariableID::from(1) => x,
VariableID::from(10) => y,
})
.constraints(BTreeMap::new())
.indicator_constraints(BTreeMap::from([(IndicatorConstraintID::from(7), ic)]))
.build()
.unwrap()
}
#[test]
fn inequality_emits_only_upper_bigm() {
let f = Function::from(linear!(1) + coeff!(-2.0));
let mut instance = single_indicator_instance(
Bound::new(0.0, 5.0).unwrap(),
Equality::LessThanOrEqualToZero,
f,
);
let new_ids = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap();
assert_eq!(new_ids.len(), 1);
let c = instance.constraints().get(&new_ids[0]).unwrap();
assert_eq!(c.equality, Equality::LessThanOrEqualToZero);
let expected = Function::from(
((linear!(1)
+ Linear::single_term(
LinearMonomial::Variable(VariableID::from(10)),
coeff!(3.0),
))
.unwrap()
+ coeff!(-5.0))
.unwrap(), );
assert_abs_diff_eq!(c.function(), &expected);
assert_eq!(
instance
.constraint_collection()
.context()
.provenance(new_ids[0]),
&[Provenance::IndicatorConstraint(
IndicatorConstraintID::from(7)
)]
);
assert!(instance.indicator_constraints().is_empty());
let (_, reason) = instance
.removed_indicator_constraints()
.get(&IndicatorConstraintID::from(7))
.expect("indicator retained as removed");
assert_eq!(
reason.reason,
"ommx.Instance.convert_indicator_to_constraint"
);
assert_eq!(
reason.parameters.get("constraint_ids").map(String::as_str),
Some(new_ids[0].into_inner().to_string().as_str())
);
}
#[test]
fn equality_emits_both_sides_when_bounds_straddle_zero() {
let f = Function::from(linear!(1) + coeff!(-2.0));
let mut instance =
single_indicator_instance(Bound::new(0.0, 5.0).unwrap(), Equality::EqualToZero, f);
let new_ids = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap();
assert_eq!(new_ids.len(), 2);
let upper = instance.constraints().get(&new_ids[0]).unwrap();
assert_eq!(upper.equality, Equality::LessThanOrEqualToZero);
let expected_upper = Function::from(
((linear!(1)
+ Linear::single_term(
LinearMonomial::Variable(VariableID::from(10)),
coeff!(3.0),
))
.unwrap()
+ coeff!(-5.0))
.unwrap(),
);
assert_abs_diff_eq!(upper.function(), &expected_upper);
let lower = instance.constraints().get(&new_ids[1]).unwrap();
assert_eq!(lower.equality, Equality::LessThanOrEqualToZero);
let expected_lower = Function::from(
Linear::single_term(LinearMonomial::Variable(VariableID::from(1)), coeff!(-1.0))
+ Linear::single_term(LinearMonomial::Variable(VariableID::from(10)), coeff!(2.0)),
);
assert_abs_diff_eq!(lower.function(), &expected_lower);
}
#[test]
fn redundant_side_is_skipped() {
let f = Function::from(linear!(1) + coeff!(-10.0));
let mut instance = single_indicator_instance(
Bound::new(0.0, 5.0).unwrap(),
Equality::LessThanOrEqualToZero,
f,
);
let before_constraints = instance.constraints().clone();
let new_ids = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap();
assert!(
new_ids.is_empty(),
"redundant indicator should emit nothing"
);
assert_eq!(
instance.constraints(),
&before_constraints,
"no new constraints added for redundant indicator"
);
let (_, reason) = instance
.removed_indicator_constraints()
.get(&IndicatorConstraintID::from(7))
.unwrap();
assert_eq!(
reason.parameters.get("constraint_ids").map(String::as_str),
Some(""),
"constraint_ids should be empty when no big-M was emitted"
);
}
#[test]
fn infinite_bound_is_rejected_without_mutation() {
let x = DecisionVariable::continuous();
let y = DecisionVariable::binary();
let ic = IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
Function::from(linear!(1)),
);
let mut instance = Instance::builder()
.sense(Sense::Minimize)
.objective(Function::from(linear!(1)))
.decision_variables(btreemap! {
VariableID::from(1) => x,
VariableID::from(10) => y,
})
.constraints(BTreeMap::new())
.indicator_constraints(BTreeMap::from([(IndicatorConstraintID::from(7), ic)]))
.build()
.unwrap();
let before_vars = instance.decision_variables.clone();
let before_constraints = instance.constraints().clone();
let before_indicators = instance.indicator_constraints().clone();
let err = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap_err();
assert!(err.to_string().contains("non-finite"));
assert_eq!(instance.decision_variables, before_vars);
assert_eq!(instance.constraints(), &before_constraints);
assert_eq!(instance.indicator_constraints(), &before_indicators);
}
#[test]
fn side_arithmetic_overflow_is_rejected_without_mutation() {
let y = VariableID::from(10);
let huge_negative = Coefficient::try_from(-f64::MAX).unwrap();
let f = (Function::from(Linear::single_term(
LinearMonomial::Variable(y),
huge_negative,
)) + coeff!(1.0))
.unwrap();
let mut instance =
single_indicator_instance(Bound::new(0.0, 1.0).unwrap(), Equality::EqualToZero, f);
let before_constraints = instance.constraints().clone();
let before_indicators = instance.indicator_constraints().clone();
let err = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap_err();
assert!(err.to_string().contains("Coefficient must be finite"));
assert_eq!(instance.constraints(), &before_constraints);
assert_eq!(instance.indicator_constraints(), &before_indicators);
assert!(instance.removed_indicator_constraints().is_empty());
}
#[test]
fn semi_continuous_variables_in_function_are_rejected() {
let x_semi = DecisionVariable::new(
Kind::SemiContinuous,
Bound::new(2.0, 5.0).unwrap(),
crate::ATol::default(),
)
.unwrap();
let y = DecisionVariable::binary();
let ic = IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
(Function::from(Linear::single_term(
LinearMonomial::Variable(VariableID::from(1)),
coeff!(-1.0),
)) + coeff!(0.5))
.unwrap(),
);
let mut instance = Instance::builder()
.sense(Sense::Minimize)
.objective(Function::from(linear!(1)))
.decision_variables(btreemap! {
VariableID::from(1) => x_semi,
VariableID::from(10) => y,
})
.constraints(BTreeMap::new())
.indicator_constraints(BTreeMap::from([(IndicatorConstraintID::from(7), ic)]))
.build()
.unwrap();
let before_constraints = instance.constraints().clone();
let err = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(7))
.unwrap_err();
let msg = err.to_string();
assert!(
msg.contains("semi-continuous") && msg.contains("not supported"),
"expected semi-not-supported error, got: {msg}"
);
assert!(instance
.indicator_constraints()
.contains_key(&IndicatorConstraintID::from(7)));
assert_eq!(instance.constraints(), &before_constraints);
}
#[test]
fn missing_id_errors_without_mutating_state() {
let f = Function::from(linear!(1) + coeff!(-2.0));
let mut instance = single_indicator_instance(
Bound::new(0.0, 5.0).unwrap(),
Equality::LessThanOrEqualToZero,
f,
);
let before_indicators = instance.indicator_constraints().clone();
let before_constraints = instance.constraints().clone();
let err = instance
.convert_indicator_to_constraint(IndicatorConstraintID::from(999))
.unwrap_err();
assert!(err.to_string().contains("999"));
assert_eq!(instance.indicator_constraints(), &before_indicators);
assert_eq!(instance.constraints(), &before_constraints);
}
#[test]
fn bulk_conversion_returns_per_indicator_ids() {
let x = DecisionVariable::new(
Kind::Continuous,
Bound::new(0.0, 5.0).unwrap(),
crate::ATol::default(),
)
.unwrap();
let y = DecisionVariable::binary();
let f = || Function::from(linear!(1) + coeff!(-2.0));
let ic_le =
IndicatorConstraint::new(VariableID::from(10), Equality::LessThanOrEqualToZero, f());
let ic_eq = IndicatorConstraint::new(VariableID::from(10), Equality::EqualToZero, f());
let mut instance = Instance::builder()
.sense(Sense::Minimize)
.objective(Function::from(linear!(1)))
.decision_variables(btreemap! {
VariableID::from(1) => x,
VariableID::from(10) => y,
})
.constraints(BTreeMap::new())
.indicator_constraints(BTreeMap::from([
(IndicatorConstraintID::from(1), ic_le),
(IndicatorConstraintID::from(2), ic_eq),
]))
.build()
.unwrap();
let result = instance.convert_all_indicators_to_constraints().unwrap();
assert_eq!(result.len(), 2);
assert_eq!(result[&IndicatorConstraintID::from(1)].len(), 1);
assert_eq!(result[&IndicatorConstraintID::from(2)].len(), 2);
assert!(instance.indicator_constraints().is_empty());
assert_eq!(instance.removed_indicator_constraints().len(), 2);
}
#[test]
fn bulk_conversion_is_atomic_on_error() {
let x1 = DecisionVariable::new(
Kind::Continuous,
Bound::new(0.0, 5.0).unwrap(),
crate::ATol::default(),
)
.unwrap();
let x2 = DecisionVariable::continuous(); let y = DecisionVariable::binary();
let ic_ok = IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
Function::from(linear!(1) + coeff!(-2.0)),
);
let ic_bad = IndicatorConstraint::new(
VariableID::from(10),
Equality::LessThanOrEqualToZero,
Function::from(linear!(2)),
);
let mut instance = Instance::builder()
.sense(Sense::Minimize)
.objective(Function::from(linear!(1)))
.decision_variables(btreemap! {
VariableID::from(1) => x1,
VariableID::from(2) => x2,
VariableID::from(10) => y,
})
.constraints(BTreeMap::new())
.indicator_constraints(BTreeMap::from([
(IndicatorConstraintID::from(1), ic_ok),
(IndicatorConstraintID::from(2), ic_bad),
]))
.build()
.unwrap();
let before_indicators = instance.indicator_constraints().clone();
let before_constraints = instance.constraints().clone();
let err = instance
.convert_all_indicators_to_constraints()
.unwrap_err();
assert!(err.to_string().contains("non-finite"));
assert_eq!(instance.indicator_constraints(), &before_indicators);
assert_eq!(instance.constraints(), &before_constraints);
assert!(instance.removed_indicator_constraints().is_empty());
}
}