oximo_core/
soc.rs

1use oximo_expr::{
2    ExprArena, ExprId, LinearTerms, ModelId, QuadraticTerms, VarId, 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
12/// A model-bound handle to an explicit second-order-cone constraint.
13#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
14pub struct SocConstraintHandle {
15    id: SocConstraintId,
16    model_id: ModelId,
17}
18
19impl SocConstraintHandle {
20    pub(crate) const fn new(id: SocConstraintId, model_id: ModelId) -> Self {
21        Self { id, model_id }
22    }
23
24    #[must_use]
25    pub const fn id(self) -> SocConstraintId {
26        self.id
27    }
28
29    #[must_use]
30    pub const fn model_id(self) -> ModelId {
31        self.model_id
32    }
33
34    #[must_use]
35    pub fn index(self) -> usize {
36        self.id.index()
37    }
38}
39
40impl From<SocConstraintHandle> for SocConstraintId {
41    fn from(value: SocConstraintHandle) -> Self {
42        value.id
43    }
44}
45
46impl PartialEq<SocConstraintId> for SocConstraintHandle {
47    fn eq(&self, other: &SocConstraintId) -> bool {
48        self.id == *other
49    }
50}
51
52impl PartialEq<SocConstraintHandle> for SocConstraintId {
53    fn eq(&self, other: &SocConstraintHandle) -> bool {
54        *self == other.id
55    }
56}
57
58impl SocConstraintId {
59    #[inline]
60    pub fn index(self) -> usize {
61        self.0 as usize
62    }
63}
64
65// TODO: Support rotated cones
66
67/// An explicit second-order cone constraint `||terms||_2 <= bound`.
68///
69/// Every member of `terms` and the `bound` must be affine. This is validated
70/// when the constraint is registered via [`crate::Model::add_soc_constraint`].
71/// Rotated cones (`2uv >= ||w||^2`) are not supported yet.
72#[derive(Clone, Debug)]
73pub struct SocConstraint {
74    pub name: SmolStr,
75    pub terms: Vec<ExprId>,
76    pub bound: ExprId,
77    pub active: bool,
78}
79
80/// Normalized second-order cone data: `|| A x + a ||_2 <= b'x + beta`, one
81/// [`LinearTerms`] per row of `A x + a` plus one for the bound side. Produced
82/// by shared solver preparation for algebraic and explicit cones.
83#[derive(Clone, Debug)]
84pub struct SocForm {
85    pub terms: Vec<LinearTerms<'static>>,
86    pub bound: LinearTerms<'static>,
87}
88
89/// Extract and validate the diagonal quadratic form shared by SOC recognition
90/// and model-kind inference.
91fn soc_quadratic(vars: &[Variable], c: &Constraint, q: &QuadraticTerms) -> Option<(VarId, f64)> {
92    let (sense, rhs) = c.as_single()?;
93    if sense != Sense::Le {
94        return None;
95    }
96    if !q.linear.is_empty() || q.constant - rhs != 0.0 {
97        return None;
98    }
99
100    let mut positives = 0;
101    let mut negative: Option<(VarId, f64)> = None;
102    for &(row, col, h) in &q.hessian {
103        if row != col {
104            return None;
105        }
106        let coef = h / 2.0;
107        if coef > 0.0 {
108            positives += 1;
109        } else if coef < 0.0 {
110            if negative.is_some() {
111                return None;
112            }
113            negative = Some((row, -coef));
114        }
115    }
116    let (t, n) = negative?;
117    if positives == 0 || vars[t.index()].lb < 0.0 {
118        return None;
119    }
120    Some((t, n))
121}
122
123/// Whether an algebraic constraint has the supported detected-SOC shape.
124///
125/// This does not materialize a [`SocForm`]. Model-kind
126/// inference only needs this predicate and can avoid allocating one
127/// `LinearTerms` coefficient vector per cone member.
128pub(crate) fn is_detected_soc(arena: &ExprArena, vars: &[Variable], c: &Constraint) -> bool {
129    if !matches!(c.as_single(), Some((Sense::Le, _))) {
130        return false;
131    }
132    extract_quadratic(arena, c.lhs).is_some_and(|q| soc_quadratic(vars, c, &q).is_some())
133}
134
135// TODO: Here we are deliberately conservative and purely structural
136
137/// Recognize an algebraic quadratic constraint as second-order-cone shaped.
138///
139/// A constraint is recognized iff:
140///
141/// - it is single-sided `lhs <= rhs` (no ranges, `>=`, or equalities),
142/// - `lhs - rhs` is a pure quadratic form: no linear terms, no constant,
143/// - the Hessian is diagonal with exactly one negative entry `-n` (on the
144///   bound variable `t`) and at least one positive entry `p_i`,
145/// - `t` has lower bound `>= 0`.
146///
147/// That is `sum_i p_i x_i^2 <= n t^2` with `t >= 0`, equivalent to
148/// `|| sqrt(p_i/n) x_i ||_2 <= t`. Cross-term (Cholesky-factorized) quadratic
149/// forms are not detected, they classify as QCP instead.
150///
151/// Backend hook for recognizing a row that has already been decomposed.
152/// `q` must describe `c.lhs` at the current parameter values.
153#[doc(hidden)]
154pub fn __detect_soc_from_quadratic(
155    vars: &[Variable],
156    c: &Constraint,
157    q: &QuadraticTerms,
158) -> Option<SocForm> {
159    let (t, n) = soc_quadratic(vars, c, q)?;
160    let terms = q
161        .hessian
162        .iter()
163        .filter_map(|&(row, _, h)| {
164            let coef = h / 2.0;
165            (coef > 0.0).then(|| LinearTerms {
166                coeffs: vec![(row, (coef / n).sqrt())].into(),
167                constant: 0.0,
168            })
169        })
170        .collect();
171    let bound = LinearTerms { coeffs: vec![(t, 1.0)].into(), constant: 0.0 };
172    Some(SocForm { terms, bound })
173}
oximo_core/soc.rs

oximo_core/
soc.rs
