oximo_core/
soc.rs

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

oximo_core/
soc.rs
