problemreductions/models/algebraic/
qubo.rs

1//! QUBO (Quadratic Unconstrained Binary Optimization) problem implementation.
2//!
3//! QUBO minimizes a quadratic function over binary variables.
4
5use crate::registry::{FieldInfo, ProblemSchemaEntry};
6use crate::traits::{OptimizationProblem, Problem};
7use crate::types::{Direction, SolutionSize, WeightElement};
8use serde::{Deserialize, Serialize};
9
10inventory::submit! {
11    ProblemSchemaEntry {
12        name: "QUBO",
13        module_path: module_path!(),
14        description: "Minimize quadratic unconstrained binary objective",
15        fields: &[
16            FieldInfo { name: "num_vars", type_name: "usize", description: "Number of binary variables" },
17            FieldInfo { name: "matrix", type_name: "Vec<Vec<W>>", description: "Upper-triangular Q matrix" },
18        ],
19    }
20}
21
22/// The QUBO (Quadratic Unconstrained Binary Optimization) problem.
23///
24/// Given n binary variables x_i ∈ {0, 1} and a matrix Q,
25/// minimize the quadratic form:
26///
27/// f(x) = Σ_i Σ_j Q_ij * x_i * x_j = x^T Q x
28///
29/// The matrix Q is typically upper triangular, with diagonal elements
30/// representing linear terms and off-diagonal elements representing
31/// quadratic interactions.
32///
33/// # Example
34///
35/// ```
36/// use problemreductions::models::algebraic::QUBO;
37/// use problemreductions::{Problem, Solver, BruteForce};
38///
39/// // Q matrix: minimize x0 - 2*x1 + x0*x1
40/// // Q = [[1, 1], [0, -2]]
41/// let problem = QUBO::from_matrix(vec![
42///     vec![1.0, 1.0],
43///     vec![0.0, -2.0],
44/// ]);
45///
46/// let solver = BruteForce::new();
47/// let solutions = solver.find_all_best(&problem);
48///
49/// // Optimal is x = [0, 1] with value -2
50/// assert!(solutions.contains(&vec![0, 1]));
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct QUBO<W = f64> {
54    /// Number of variables.
55    num_vars: usize,
56    /// Q matrix stored as upper triangular (row-major).
57    /// `Q[i][j]` for i <= j represents the coefficient of x_i * x_j
58    matrix: Vec<Vec<W>>,
59}
60
61impl<W: Clone + Default> QUBO<W> {
62    /// Create a QUBO problem from a full matrix.
63    ///
64    /// The matrix should be square. Only the upper triangular part
65    /// (including diagonal) is used.
66    pub fn from_matrix(matrix: Vec<Vec<W>>) -> Self {
67        let num_vars = matrix.len();
68        Self { num_vars, matrix }
69    }
70
71    /// Create a QUBO from linear and quadratic terms.
72    ///
73    /// # Arguments
74    /// * `linear` - Linear coefficients (diagonal of Q)
75    /// * `quadratic` - Quadratic coefficients as ((i, j), value) for i < j
76    pub fn new(linear: Vec<W>, quadratic: Vec<((usize, usize), W)>) -> Self
77    where
78        W: num_traits::Zero,
79    {
80        let num_vars = linear.len();
81        let mut matrix = vec![vec![W::zero(); num_vars]; num_vars];
82
83        // Set diagonal (linear terms)
84        for (i, val) in linear.into_iter().enumerate() {
85            matrix[i][i] = val;
86        }
87
88        // Set off-diagonal (quadratic terms)
89        for ((i, j), val) in quadratic {
90            if i < j {
91                matrix[i][j] = val;
92            } else {
93                matrix[j][i] = val;
94            }
95        }
96
97        Self { num_vars, matrix }
98    }
99
100    /// Get the number of variables.
101    pub fn num_vars(&self) -> usize {
102        self.num_vars
103    }
104
105    /// Get the Q matrix.
106    pub fn matrix(&self) -> &[Vec<W>] {
107        &self.matrix
108    }
109
110    /// Get a specific matrix element `Q[i][j]`.
111    pub fn get(&self, i: usize, j: usize) -> Option<&W> {
112        self.matrix.get(i).and_then(|row| row.get(j))
113    }
114}
115
116impl<W> QUBO<W>
117where
118    W: Clone + num_traits::Zero + std::ops::AddAssign + std::ops::Mul<Output = W>,
119{
120    /// Evaluate the QUBO objective for a configuration.
121    pub fn evaluate(&self, config: &[usize]) -> W {
122        let mut value = W::zero();
123
124        for i in 0..self.num_vars {
125            let x_i = config.get(i).copied().unwrap_or(0);
126            if x_i == 0 {
127                continue;
128            }
129
130            for j in i..self.num_vars {
131                let x_j = config.get(j).copied().unwrap_or(0);
132                if x_j == 0 {
133                    continue;
134                }
135
136                if let Some(q_ij) = self.matrix.get(i).and_then(|row| row.get(j)) {
137                    value += q_ij.clone();
138                }
139            }
140        }
141
142        value
143    }
144}
145
146impl<W> Problem for QUBO<W>
147where
148    W: WeightElement
149        + crate::variant::VariantParam
150        + PartialOrd
151        + num_traits::Num
152        + num_traits::Zero
153        + num_traits::Bounded
154        + std::ops::AddAssign
155        + std::ops::Mul<Output = W>,
156{
157    const NAME: &'static str = "QUBO";
158    type Metric = SolutionSize<W::Sum>;
159
160    fn dims(&self) -> Vec<usize> {
161        vec![2; self.num_vars]
162    }
163
164    fn evaluate(&self, config: &[usize]) -> SolutionSize<W::Sum> {
165        SolutionSize::Valid(self.evaluate(config).to_sum())
166    }
167
168    fn variant() -> Vec<(&'static str, &'static str)> {
169        crate::variant_params![W]
170    }
171}
172
173impl<W> OptimizationProblem for QUBO<W>
174where
175    W: WeightElement
176        + crate::variant::VariantParam
177        + PartialOrd
178        + num_traits::Num
179        + num_traits::Zero
180        + num_traits::Bounded
181        + std::ops::AddAssign
182        + std::ops::Mul<Output = W>,
183{
184    type Value = W::Sum;
185
186    fn direction(&self) -> Direction {
187        Direction::Minimize
188    }
189}
190
191crate::declare_variants! {
192    QUBO<f64> => "2^num_vars",
193}
194
195#[cfg(test)]
196#[path = "../../unit_tests/models/algebraic/qubo.rs"]
197mod tests;
problemreductions/models/algebraic/qubo.rs

problemreductions/models/algebraic/
qubo.rs
