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

problemreductions/models/algebraic/
qubo.rs
