oximo_core/reformulation/
indicator.rs

1//! Explicit indicator-to-linear Big-M reformulation.
2
3use std::cell::Ref;
4
5use oximo_expr::{Expr, ExprId, ExprNode, extract_linear};
6use smol_str::SmolStr;
7
8use crate::constraint::{ConstraintId, Relate};
9use crate::domain::Domain;
10use crate::indicator::{IndicatorConstraint, IndicatorConstraintHandle, IndicatorConstraintId};
11use crate::model::Model;
12use crate::reformulation::sos::{ReformulatedModel, ReformulationError};
13use crate::var::Variable;
14
15/// Settings for explicit indicator-to-MILP reformulation.
16#[derive(Copy, Clone, Debug, Default, PartialEq)]
17pub struct IndicatorReformulationOptions {
18    fallback_big_m: Option<f64>,
19}
20
21impl IndicatorReformulationOptions {
22    /// Use `big_m` as the row M only where finite variable bounds cannot derive one.
23    #[must_use]
24    pub const fn with_fallback_big_m(mut self, big_m: f64) -> Self {
25        self.fallback_big_m = Some(big_m);
26        self
27    }
28
29    #[must_use]
30    pub const fn fallback_big_m(self) -> Option<f64> {
31        self.fallback_big_m
32    }
33}
34
35/// IDs appended while replacing one source indicator.
36#[derive(Clone, Debug, PartialEq, Eq)]
37pub struct IndicatorReformulationArtifacts {
38    pub source: IndicatorConstraintId,
39    pub constraints: Vec<ConstraintId>,
40}
41
42#[derive(Clone, Debug)]
43struct PlannedIndicator {
44    source: IndicatorConstraintId,
45    lower_m: Option<f64>,
46    upper_m: Option<f64>,
47}
48
49#[derive(Debug)]
50struct IndicatorPlan(Vec<PlannedIndicator>);
51
52impl IndicatorPlan {
53    fn one(
54        model: &Model,
55        id: IndicatorConstraintId,
56        options: IndicatorReformulationOptions,
57    ) -> Result<Self, ReformulationError> {
58        validate_options(options)?;
59        let constraints = model.indicator_constraints.borrow();
60        let source = constraints
61            .get(id.index())
62            .ok_or(ReformulationError::UnknownIndicatorConstraint(id.index()))?;
63        let entries =
64            if source.active { vec![plan_one(model, id, source, options)?] } else { Vec::new() };
65        Ok(Self(entries))
66    }
67
68    fn all(
69        model: &Model,
70        options: IndicatorReformulationOptions,
71    ) -> Result<Self, ReformulationError> {
72        validate_options(options)?;
73        let constraints = model.indicator_constraints.borrow();
74        let mut entries = Vec::new();
75        for (index, source) in constraints.iter().enumerate() {
76            if source.active {
77                entries.push(plan_one(
78                    model,
79                    IndicatorConstraintId(u32::try_from(index).expect("indicator ID overflow")),
80                    source,
81                    options,
82                )?);
83            }
84        }
85        Ok(Self(entries))
86    }
87
88    fn apply(self, model: &Model) -> Vec<IndicatorReformulationArtifacts> {
89        let mut artifacts = Vec::with_capacity(self.0.len());
90        for planned in self.0 {
91            artifacts.push(planned.apply(model));
92        }
93        if !artifacts.is_empty() {
94            model.invalidate_kind();
95        }
96        model.indicator_reformulations.borrow_mut().extend(artifacts.iter().cloned());
97        artifacts
98    }
99}
100
101fn validate_options(options: IndicatorReformulationOptions) -> Result<(), ReformulationError> {
102    if let Some(big_m) = options.fallback_big_m
103        && (!big_m.is_finite() || big_m <= 0.0)
104    {
105        return Err(ReformulationError::InvalidFallbackBigM(big_m));
106    }
107    Ok(())
108}
109
110fn plan_one(
111    model: &Model,
112    id: IndicatorConstraintId,
113    source: &IndicatorConstraint,
114    options: IndicatorReformulationOptions,
115) -> Result<PlannedIndicator, ReformulationError> {
116    if source.lower == f64::INFINITY || source.upper == f64::NEG_INFINITY {
117        return Err(ReformulationError::InvalidIndicatorBounds { constraint: source.name.clone() });
118    }
119    let arena = model.arena.borrow();
120    if contains_parameter(&arena, source.lhs) {
121        return Err(ReformulationError::ParameterDependentIndicator {
122            constraint: source.name.clone(),
123        });
124    }
125    let terms = extract_linear(&arena, source.lhs).ok_or_else(|| {
126        ReformulationError::InvalidIndicatorExpression { constraint: source.name.clone() }
127    })?;
128    if !terms.constant.is_finite() || terms.coeffs.iter().any(|(_, c)| !c.is_finite()) {
129        return Err(ReformulationError::InvalidIndicatorExpression {
130            constraint: source.name.clone(),
131        });
132    }
133    let variables = model.variables.borrow();
134    let inactive = if source.active_value { 0.0 } else { 1.0 };
135    let mut minimum = terms.constant;
136    let mut maximum = terms.constant;
137    for &(variable, coefficient) in terms.coeffs.iter() {
138        if coefficient == 0.0 {
139            continue;
140        }
141        let (lower, upper) = effective_bounds(&variables[variable.index()]);
142        let (lower, upper) =
143            if variable == source.trigger { (inactive, inactive) } else { (lower, upper) };
144        let (min_bound, max_bound) =
145            if coefficient >= 0.0 { (lower, upper) } else { (upper, lower) };
146        minimum += coefficient * min_bound;
147        maximum += coefficient * max_bound;
148    }
149    if minimum.is_nan() || maximum.is_nan() {
150        return Err(ReformulationError::InvalidIndicatorExpression {
151            constraint: source.name.clone(),
152        });
153    }
154    let lower_m = if source.lower.is_finite() {
155        Some(m_for_side(source.lower - minimum, source, "lower", options)?)
156    } else {
157        None
158    };
159    let upper_m = if source.upper.is_finite() {
160        Some(m_for_side(maximum - source.upper, source, "upper", options)?)
161    } else {
162        None
163    };
164    Ok(PlannedIndicator { source: id, lower_m, upper_m })
165}
166
167fn m_for_side(
168    required: f64,
169    source: &IndicatorConstraint,
170    side: &'static str,
171    options: IndicatorReformulationOptions,
172) -> Result<f64, ReformulationError> {
173    if required.is_finite() {
174        Ok(required.max(0.0))
175    } else if let Some(big_m) = options.fallback_big_m {
176        Ok(big_m)
177    } else {
178        Err(ReformulationError::MissingIndicatorBigM { constraint: source.name.clone(), side })
179    }
180}
181
182fn effective_bounds(variable: &Variable) -> (f64, f64) {
183    match variable.domain {
184        Domain::SemiContinuous { threshold } | Domain::SemiInteger { threshold } => {
185            (threshold.min(0.0), variable.ub.max(0.0))
186        }
187        Domain::Real | Domain::Integer | Domain::Binary => (variable.lb, variable.ub),
188    }
189}
190
191fn contains_parameter(arena: &oximo_expr::ExprArena, root: ExprId) -> bool {
192    let mut stack = vec![root];
193    while let Some(id) = stack.pop() {
194        match arena.get(id) {
195            ExprNode::Param(_) => return true,
196            ExprNode::Add(children)
197            | ExprNode::Mul(children)
198            | ExprNode::Min(children)
199            | ExprNode::Max(children) => stack.extend(children.iter().copied()),
200            ExprNode::Unary(_, child) => stack.push(*child),
201            ExprNode::Pow(left, right)
202            | ExprNode::Div(left, right)
203            | ExprNode::Atan2(left, right) => {
204                stack.push(*left);
205                stack.push(*right);
206            }
207            ExprNode::Const(_) | ExprNode::Var(_) | ExprNode::Linear { .. } => {}
208        }
209    }
210    false
211}
212
213impl PlannedIndicator {
214    fn apply(self, model: &Model) -> IndicatorReformulationArtifacts {
215        let source = model.indicator_constraints.borrow()[self.source.index()].clone();
216        let lhs = Expr::new(source.lhs, &model.arena);
217        let trigger = Expr::from_var(&model.arena, source.trigger);
218        let inactive = if source.active_value { 1.0 - trigger } else { trigger };
219        let mut generated = Vec::with_capacity(2);
220        // A zero M still needs a row: the body can differ between trigger values.
221        if let Some(big_m) = self.lower_m {
222            let name = unique_constraint_name(
223                model,
224                &format!("__oximo_indicator{}_lower", self.source.index()),
225            );
226            generated
227                .push(model.__add_constraint(name, lhs.ge(source.lower - big_m * inactive)).id());
228        }
229        if let Some(big_m) = self.upper_m {
230            let name = unique_constraint_name(
231                model,
232                &format!("__oximo_indicator{}_upper", self.source.index()),
233            );
234            generated
235                .push(model.__add_constraint(name, lhs.le(source.upper + big_m * inactive)).id());
236        }
237        model.indicator_constraints.borrow_mut()[self.source.index()].active = false;
238        IndicatorReformulationArtifacts { source: self.source, constraints: generated }
239    }
240}
241
242fn unique_constraint_name(model: &Model, base: &str) -> SmolStr {
243    if model.constraint_id(base).is_none() {
244        return base.into();
245    }
246    for suffix in 1_u64.. {
247        let candidate = format!("{base}_{suffix}");
248        if model.constraint_id(&candidate).is_none() {
249            return candidate.into();
250        }
251    }
252    unreachable!("u64 name suffix space exhausted")
253}
254
255impl IndicatorConstraintHandle<'_> {
256    /// Clone the model and replace this active indicator with Big-M rows.
257    ///
258    /// # Errors
259    /// Returns a reformulation error if the body, bounds, or options are invalid.
260    pub fn to_reformulated_model(
261        self,
262        options: IndicatorReformulationOptions,
263    ) -> Result<ReformulatedModel, ReformulationError> {
264        self.model.to_reformulated_indicator_constraint_model(self.id, options)
265    }
266
267    /// Replace this indicator in place. Returns `None` when it is already inactive.
268    ///
269    /// # Errors
270    /// Returns an error before mutation if the selected indicator is invalid.
271    pub fn reformulate(
272        self,
273        options: IndicatorReformulationOptions,
274    ) -> Result<Option<IndicatorReformulationArtifacts>, ReformulationError> {
275        self.model.reformulate_indicator_constraint(self.id, options)
276    }
277}
278
279impl Model {
280    /// Clone the model and replace one indicator while preserving its source ID.
281    ///
282    /// # Errors
283    /// Returns a reformulation error if the ID, body, bounds, or options are invalid.
284    pub fn to_reformulated_indicator_constraint_model(
285        &self,
286        id: IndicatorConstraintId,
287        options: IndicatorReformulationOptions,
288    ) -> Result<ReformulatedModel, ReformulationError> {
289        let plan = IndicatorPlan::one(self, id, options)?;
290        let model = self.clone_preserving_ids_with_capacity(0, plan.0.len() * 2, plan.0.len() * 8);
291        plan.apply(&model);
292        Ok(ReformulatedModel { model })
293    }
294
295    /// Replace one indicator in place after validating its complete reformulation.
296    /// Returns `None` if the source indicator is already inactive.
297    ///
298    /// # Errors
299    /// Returns an error before mutation if the selected indicator is invalid.
300    pub fn reformulate_indicator_constraint(
301        &self,
302        id: IndicatorConstraintId,
303        options: IndicatorReformulationOptions,
304    ) -> Result<Option<IndicatorReformulationArtifacts>, ReformulationError> {
305        let plan = IndicatorPlan::one(self, id, options)?;
306        Ok(plan.apply(self).pop())
307    }
308
309    /// Clone the model and replace every active indicator in ID order.
310    ///
311    /// # Errors
312    /// Returns an error without producing a partial clone if any indicator is invalid.
313    pub fn to_reformulated_indicator_model(
314        &self,
315        options: IndicatorReformulationOptions,
316    ) -> Result<ReformulatedModel, ReformulationError> {
317        let plan = IndicatorPlan::all(self, options)?;
318        let model = self.clone_preserving_ids_with_capacity(0, plan.0.len() * 2, plan.0.len() * 8);
319        plan.apply(&model);
320        Ok(ReformulatedModel { model })
321    }
322
323    /// Replace every active indicator after validating the complete model plan.
324    ///
325    /// # Errors
326    /// Returns an error without mutating the model if any indicator is invalid.
327    pub fn reformulate_indicators(
328        &self,
329        options: IndicatorReformulationOptions,
330    ) -> Result<Vec<IndicatorReformulationArtifacts>, ReformulationError> {
331        let plan = IndicatorPlan::all(self, options)?;
332        Ok(plan.apply(self))
333    }
334
335    /// Complete indicator reformulation history retained by this model.
336    #[must_use]
337    pub fn indicator_reformulations(&self) -> Ref<'_, [IndicatorReformulationArtifacts]> {
338        Ref::map(self.indicator_reformulations.borrow(), Vec::as_slice)
339    }
340}
oximo_core/reformulation/indicator.rs

oximo_core/reformulation/
indicator.rs
