oximo_core/
soc.rs

1use oximo_expr::{ExprArena, ExprId, LinearTerms, VarId, extract_linear, extract_quadratic};
2use smol_str::SmolStr;
3
4use crate::constraint::{Constraint, Sense};
5use crate::var::Variable;
6
7#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
8pub struct SocConstraintId(pub u32);
9
10impl SocConstraintId {
11    #[inline]
12    pub fn index(self) -> usize {
13        self.0 as usize
14    }
15}
16
17// TODO: Support rotated cones
18
19/// An explicit second-order cone constraint `||terms||_2 <= bound`.
20///
21/// Every member of `terms` and the `bound` must be affine. This is validated
22/// when the constraint is registered via [`crate::Model::add_soc_constraint`].
23/// Rotated cones (`2uv >= ||w||^2`) are not supported yet.
24#[derive(Clone, Debug)]
25pub struct SocConstraint {
26    pub name: SmolStr,
27    pub terms: Vec<ExprId>,
28    pub bound: ExprId,
29    pub active: bool,
30}
31
32/// Normalized second-order cone data: `|| A x + a ||_2 <= b'x + beta`, one
33/// [`LinearTerms`] per row of `A x + a` plus one for the bound side. Produced
34/// by [`detect_soc`] (algebraic quadratic constraints) and
35/// [`explicit_soc_form`] ([`SocConstraint`]s), so backends translate both
36/// through a single shape.
37#[derive(Clone, Debug)]
38pub struct SocForm {
39    pub terms: Vec<LinearTerms>,
40    pub bound: LinearTerms,
41}
42
43// TODO: Here we are deliberately conservative and purely structural
44
45/// Recognize an algebraic quadratic constraint as second-order-cone shaped.
46///
47/// A constraint is recognized iff:
48///
49/// - it is single-sided `lhs <= rhs` (no ranges, `>=`, or equalities),
50/// - `lhs - rhs` is a pure quadratic form: no linear terms, no constant,
51/// - the Hessian is diagonal with exactly one negative entry `-n` (on the
52///   bound variable `t`) and at least one positive entry `p_i`,
53/// - `t` has lower bound `>= 0`.
54///
55/// That is `sum_i p_i x_i^2 <= n t^2` with `t >= 0`, equivalent to
56/// `|| sqrt(p_i/n) x_i ||_2 <= t`. Cross-term (Cholesky-factorized) quadratic
57/// forms are not detected, they classify as QCP instead.
58pub fn detect_soc(arena: &ExprArena, vars: &[Variable], c: &Constraint) -> Option<SocForm> {
59    let (sense, rhs) = c.as_single()?;
60    if sense != Sense::Le {
61        return None;
62    }
63    let q = extract_quadratic(arena, c.lhs)?;
64    if !q.linear.is_empty() || q.constant - rhs != 0.0 {
65        return None;
66    }
67
68    let mut positives: Vec<(VarId, f64)> = Vec::new();
69    let mut negative: Option<(VarId, f64)> = None;
70    for &(row, col, h) in &q.hessian {
71        if row != col {
72            return None;
73        }
74        let coef = h / 2.0;
75        if coef > 0.0 {
76            positives.push((row, coef));
77        } else if coef < 0.0 {
78            if negative.is_some() {
79                return None;
80            }
81            negative = Some((row, -coef));
82        }
83    }
84    let (t, n) = negative?;
85    if positives.is_empty() || vars[t.index()].lb < 0.0 {
86        return None;
87    }
88
89    let terms = positives
90        .into_iter()
91        .map(|(x, p)| LinearTerms { coeffs: vec![(x, (p / n).sqrt())], constant: 0.0 })
92        .collect();
93    let bound = LinearTerms { coeffs: vec![(t, 1.0)], constant: 0.0 };
94    Some(SocForm { terms, bound })
95}
96
97/// The normalized [`SocForm`] view of an explicit [`SocConstraint`]. Members
98/// are validated affine at registration, so this only returns `None` on a
99/// corrupted model (e.g. an `ExprId` from a different arena).
100pub fn explicit_soc_form(arena: &ExprArena, s: &SocConstraint) -> Option<SocForm> {
101    let terms = s.terms.iter().map(|&e| extract_linear(arena, e)).collect::<Option<Vec<_>>>()?;
102    let bound = extract_linear(arena, s.bound)?;
103    Some(SocForm { terms, bound })
104}
oximo_core/soc.rs

oximo_core/
soc.rs
