otspot_core/problem/
certificate.rs

1//! Proof-carrying certificate types. [`OptimalCertificate`] / [`BoundGapCertificate`]
2//! は内部ファクトリ経由でのみ生成され、保持自体が proof token になる。
3
4/// KKT optimality certificate — minted only by [`crate::qp::certificate::prove_optimal`].
5#[derive(Debug, Clone)]
6pub struct OptimalCertificate {
7    stationarity_rel: f64,
8    primal_residual_rel: f64,
9    dual_sign_violation: f64,
10    duality_gap_rel: f64,
11    tol: f64,
12}
13
14impl OptimalCertificate {
15    pub(crate) fn new(
16        stationarity_rel: f64,
17        primal_residual_rel: f64,
18        dual_sign_violation: f64,
19        duality_gap_rel: f64,
20        tol: f64,
21    ) -> Self {
22        Self {
23            stationarity_rel,
24            primal_residual_rel,
25            dual_sign_violation,
26            duality_gap_rel,
27            tol,
28        }
29    }
30
31    /// Componentwise relative stationarity: `max_j |Qx+c+Aᵀy+z|_j / scale_j`.
32    pub fn stationarity_rel(&self) -> f64 {
33        self.stationarity_rel
34    }
35
36    /// Componentwise relative primal violation: `max_i viol_i / scale_i`.
37    pub fn primal_residual_rel(&self) -> f64 {
38        self.primal_residual_rel
39    }
40
41    /// Dual-sign violation: `max_k viol_k / (1 + |v_k|)` over sign-constrained duals.
42    pub fn dual_sign_violation(&self) -> f64 {
43        self.dual_sign_violation
44    }
45
46    /// Relative duality gap: `|p_obj − d_obj| / max(|p|, |d|, 1)`.
47    pub fn duality_gap_rel(&self) -> f64 {
48        self.duality_gap_rel
49    }
50
51    /// Tolerance used when the certificate was issued.
52    pub fn tol(&self) -> f64 {
53        self.tol
54    }
55}
56
57/// Reason why `prove_optimal` failed: observed residuals + failing condition names.
58#[derive(Debug, Clone)]
59pub struct NotProven {
60    pub stationarity_rel: f64,
61    pub primal_residual_rel: f64,
62    pub bound_violation: f64,
63    pub complementarity_rel: f64,
64    pub dual_sign_violation: f64,
65    pub duality_gap_rel: f64,
66    pub tol: f64,
67    pub failing_conditions: Vec<&'static str>,
68}
69
70/// B&B gap certificate — minted by the B&B driver when no region was abandoned
71/// (`proof_uncertain == false`) and `gap_rel ≤ gap_tol`. External code cannot
72/// construct it.
73#[derive(Debug, Clone)]
74pub struct BoundGapCertificate {
75    incumbent_obj: f64,
76    lower_bound: f64,
77    gap_rel: f64,
78    gap_tol: f64,
79}
80
81impl BoundGapCertificate {
82    pub(crate) fn new(incumbent_obj: f64, lower_bound: f64, gap_rel: f64, gap_tol: f64) -> Self {
83        Self {
84            incumbent_obj,
85            lower_bound,
86            gap_rel,
87            gap_tol,
88        }
89    }
90
91    /// Best integer-feasible objective found by the search.
92    pub fn incumbent_obj(&self) -> f64 {
93        self.incumbent_obj
94    }
95
96    /// Authenticated lower bound on the global optimum at termination.
97    pub fn lower_bound(&self) -> f64 {
98        self.lower_bound
99    }
100
101    /// Relative gap: `(incumbent_obj - lower_bound) / max(1, |incumbent_obj|)`.
102    pub fn gap_rel(&self) -> f64 {
103        self.gap_rel
104    }
105
106    /// Tolerance against which the gap was checked when the certificate was issued.
107    pub fn gap_tol(&self) -> f64 {
108        self.gap_tol
109    }
110}
otspot_core/problem/certificate.rs

otspot_core/problem/
certificate.rs
