problemreductions/models/algebraic/
closest_vector_problem.rs

1//! Closest Vector Problem (CVP) implementation.
2//!
3//! Given a lattice basis B and target vector t, find integer coefficients x
4//! minimizing ‖Bx - t‖₂.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "ClosestVectorProblem",
14        display_name: "Closest Vector Problem",
15        aliases: &["CVP"],
16        dimensions: &[VariantDimension::new("weight", "i32", &["i32", "f64"])],
17        module_path: module_path!(),
18        description: "Find the closest lattice point to a target vector",
19        fields: &[
20            FieldInfo { name: "basis", type_name: "Vec<Vec<T>>", description: "Basis matrix B as column vectors" },
21            FieldInfo { name: "target", type_name: "Vec<f64>", description: "Target vector t" },
22            FieldInfo { name: "bounds", type_name: "Vec<VarBounds>", description: "Integer bounds per variable" },
23        ],
24    }
25}
26
27/// Variable bounds (None = unbounded in that direction).
28///
29/// Represents the lower and upper bounds for an integer variable.
30/// A value of `None` indicates the variable is unbounded in that direction.
31#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
32pub struct VarBounds {
33    /// Lower bound (None = -infinity).
34    pub lower: Option<i64>,
35    /// Upper bound (None = +infinity).
36    pub upper: Option<i64>,
37}
38
39impl VarBounds {
40    /// Create bounds for a binary variable: 0 <= x <= 1.
41    pub fn binary() -> Self {
42        Self {
43            lower: Some(0),
44            upper: Some(1),
45        }
46    }
47
48    /// Create bounds for a non-negative variable: x >= 0.
49    pub fn non_negative() -> Self {
50        Self {
51            lower: Some(0),
52            upper: None,
53        }
54    }
55
56    /// Create unbounded variable: -infinity < x < +infinity.
57    pub fn unbounded() -> Self {
58        Self {
59            lower: None,
60            upper: None,
61        }
62    }
63
64    /// Create bounds with explicit lower and upper: lo <= x <= hi.
65    pub fn bounded(lo: i64, hi: i64) -> Self {
66        Self {
67            lower: Some(lo),
68            upper: Some(hi),
69        }
70    }
71
72    /// Check if a value satisfies these bounds.
73    pub fn contains(&self, value: i64) -> bool {
74        if let Some(lo) = self.lower {
75            if value < lo {
76                return false;
77            }
78        }
79        if let Some(hi) = self.upper {
80            if value > hi {
81                return false;
82            }
83        }
84        true
85    }
86
87    /// Get the number of integer values in this bound range.
88    /// Returns None if unbounded in either direction.
89    pub fn num_values(&self) -> Option<usize> {
90        match (self.lower, self.upper) {
91            (Some(lo), Some(hi)) => {
92                if hi >= lo {
93                    Some((hi - lo + 1) as usize)
94                } else {
95                    Some(0)
96                }
97            }
98            _ => None,
99        }
100    }
101
102    /// Returns an exact bounded binary basis for offsets in this range.
103    ///
104    /// For a bounded variable with offsets `0..=hi-lo`, the returned weights
105    /// ensure that every bit-pattern reconstructs an in-range offset. Low-order
106    /// weights use powers of two; the final weight is capped so the maximum
107    /// reachable offset is exactly `hi-lo`.
108    pub(crate) fn exact_encoding_weights(&self) -> Vec<i64> {
109        let Some(num_values) = self.num_values() else {
110            panic!("CVP QUBO encoding requires finite variable bounds");
111        };
112        if num_values <= 1 {
113            return Vec::new();
114        }
115
116        let max_offset = (num_values - 1) as i64;
117        let num_bits = (usize::BITS - (num_values - 1).leading_zeros()) as usize;
118        let mut weights = Vec::with_capacity(num_bits);
119
120        for bit in 0..num_bits.saturating_sub(1) {
121            weights.push(1_i64 << bit);
122        }
123
124        let covered_by_lower_bits = if num_bits <= 1 {
125            0
126        } else {
127            (1_i64 << (num_bits - 1)) - 1
128        };
129        weights.push(max_offset - covered_by_lower_bits);
130        weights
131    }
132
133    /// Returns the number of encoding bits needed for the exact bounded basis.
134    pub(crate) fn num_encoding_bits(&self) -> usize {
135        self.exact_encoding_weights().len()
136    }
137}
138
139/// Closest Vector Problem (CVP).
140///
141/// Given a lattice basis B ∈ R^{m×n} and target t ∈ R^m,
142/// find integer x ∈ Z^n minimizing ‖Bx - t‖₂.
143///
144/// Variables are integer coefficients with explicit bounds for enumeration.
145/// The configuration encoding follows ILP: config[i] is an offset from bounds[i].lower.
146#[derive(Debug, Clone, Serialize, Deserialize)]
147pub struct ClosestVectorProblem<T> {
148    /// Basis matrix B stored as n column vectors, each of dimension m.
149    basis: Vec<Vec<T>>,
150    /// Target vector t ∈ R^m.
151    target: Vec<f64>,
152    /// Integer bounds per variable for enumeration.
153    bounds: Vec<VarBounds>,
154}
155
156impl<T> ClosestVectorProblem<T> {
157    /// Create a new CVP instance.
158    ///
159    /// # Arguments
160    /// * `basis` - n column vectors of dimension m
161    /// * `target` - target vector of dimension m
162    /// * `bounds` - integer bounds per variable (length n)
163    ///
164    /// # Panics
165    /// Panics if basis/bounds lengths mismatch or dimensions are inconsistent.
166    pub fn new(basis: Vec<Vec<T>>, target: Vec<f64>, bounds: Vec<VarBounds>) -> Self {
167        let n = basis.len();
168        assert_eq!(
169            bounds.len(),
170            n,
171            "bounds length must match number of basis vectors"
172        );
173        let m = target.len();
174        for (i, col) in basis.iter().enumerate() {
175            assert_eq!(
176                col.len(),
177                m,
178                "basis vector {i} has length {}, expected {m}",
179                col.len()
180            );
181        }
182        Self {
183            basis,
184            target,
185            bounds,
186        }
187    }
188
189    /// Number of basis vectors (lattice dimension n).
190    pub fn num_basis_vectors(&self) -> usize {
191        self.basis.len()
192    }
193
194    /// Dimension of the ambient space (m).
195    pub fn ambient_dimension(&self) -> usize {
196        self.target.len()
197    }
198
199    /// Access the basis matrix.
200    pub fn basis(&self) -> &[Vec<T>] {
201        &self.basis
202    }
203
204    /// Access the target vector.
205    pub fn target(&self) -> &[f64] {
206        &self.target
207    }
208
209    /// Access the variable bounds.
210    pub fn bounds(&self) -> &[VarBounds] {
211        &self.bounds
212    }
213
214    /// Returns the total number of bounded-encoding bits used by the QUBO form.
215    pub fn num_encoding_bits(&self) -> usize {
216        self.bounds.iter().map(VarBounds::num_encoding_bits).sum()
217    }
218
219    /// Convert a configuration (offsets from lower bounds) to integer values.
220    fn config_to_values(&self, config: &[usize]) -> Vec<i64> {
221        config
222            .iter()
223            .enumerate()
224            .map(|(i, &c)| {
225                let lo = self.bounds.get(i).and_then(|b| b.lower).unwrap_or(0);
226                lo + c as i64
227            })
228            .collect()
229    }
230}
231
232impl<T> Problem for ClosestVectorProblem<T>
233where
234    T: Clone
235        + Into<f64>
236        + crate::variant::VariantParam
237        + Serialize
238        + for<'de> Deserialize<'de>
239        + std::fmt::Debug
240        + 'static,
241{
242    const NAME: &'static str = "ClosestVectorProblem";
243    type Value = Min<f64>;
244
245    fn dims(&self) -> Vec<usize> {
246        self.bounds
247            .iter()
248            .map(|b| {
249                b.num_values().expect(
250                    "CVP brute-force enumeration requires all variables to have finite bounds",
251                )
252            })
253            .collect()
254    }
255
256    fn evaluate(&self, config: &[usize]) -> Min<f64> {
257        let values = self.config_to_values(config);
258        let m = self.ambient_dimension();
259        let mut diff = vec![0.0f64; m];
260        for (i, &x_i) in values.iter().enumerate() {
261            for (j, b_ji) in self.basis[i].iter().enumerate() {
262                diff[j] += x_i as f64 * b_ji.clone().into();
263            }
264        }
265        for (d, t) in diff.iter_mut().zip(self.target.iter()) {
266            *d -= t;
267        }
268        let norm = diff.iter().map(|d| d * d).sum::<f64>().sqrt();
269        Min(Some(norm))
270    }
271
272    fn variant() -> Vec<(&'static str, &'static str)> {
273        crate::variant_params![T]
274    }
275}
276
277crate::declare_variants! {
278    default ClosestVectorProblem<i32> => "2^num_basis_vectors",
279    ClosestVectorProblem<f64> => "2^num_basis_vectors",
280}
281
282#[cfg(feature = "example-db")]
283pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
284    vec![crate::example_db::specs::ModelExampleSpec {
285        id: "closest_vector_problem_i32",
286        instance: Box::new(ClosestVectorProblem::new(
287            vec![vec![2, 0], vec![1, 2]],
288            vec![2.8, 1.5],
289            vec![VarBounds::bounded(-2, 4), VarBounds::bounded(-2, 4)],
290        )),
291        optimal_config: vec![3, 3],
292        optimal_value: serde_json::json!(0.5385164807134505),
293    }]
294}
295
296#[cfg(test)]
297#[path = "../../unit_tests/models/algebraic/closest_vector_problem.rs"]
298mod tests;
problemreductions/models/algebraic/closest_vector_problem.rs

problemreductions/models/algebraic/
closest_vector_problem.rs
