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::{ConstructionError, CreateSpec, ProblemSchemaEntry, VariantDimension};
6use crate::traits::Problem;
7use crate::types::{Min, WeightElement};
8use num_traits::Zero;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "QUBO",
14        display_name: "QUBO",
15        aliases: &[],
16        dimensions: &[VariantDimension::new("weight", "i64", &["i64", "f64"])],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Minimize quadratic unconstrained binary objective",
20        fields: QuboCreateSpec::<i64>::FIELDS,
21    }
22}
23
24/// The QUBO (Quadratic Unconstrained Binary Optimization) problem.
25///
26/// Given n binary variables x_i ∈ {0, 1} and a matrix Q,
27/// minimize the quadratic form:
28///
29/// f(x) = Σ_i Σ_j Q_ij * x_i * x_j = x^T Q x
30///
31/// The matrix Q is typically upper triangular, with diagonal elements
32/// representing linear terms and off-diagonal elements representing
33/// quadratic interactions.
34///
35/// `QUBO<i64>` is the default exact-integer variant. `QUBO<f64>` stores
36/// finite floating-point coefficients. An explicit variant reduction converts
37/// exactly representable integer coefficients to `f64`.
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::algebraic::QUBO;
43/// use problemreductions::{Problem, BruteForce};
44///
45/// // Q matrix: minimize x0 - 2*x1 + x0*x1
46/// // Q = [[1, 1], [0, -2]]
47/// let problem = QUBO::from_matrix(vec![
48///     vec![1, 1],
49///     vec![0, -2],
50/// ]).unwrap();
51///
52/// let solver = BruteForce::new();
53/// let solutions = solver.find_all_witnesses(&problem).unwrap();
54///
55/// // Optimal is x = [0, 1] with value -2
56/// assert!(solutions.contains(&vec![false, true]));
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59pub struct QUBO<W = i64> {
60    /// Number of variables.
61    num_vars: usize,
62    /// Q matrix stored as upper triangular (row-major).
63    /// `Q[i][j]` for i <= j represents the coefficient of x_i * x_j
64    matrix: Vec<Vec<W>>,
65}
66
67#[derive(Debug, Deserialize, crate::CreateSpec)]
68struct QuboCreateSpec<W> {
69    /// Q matrix; the number of variables is its row count.
70    #[create(codec = "semicolon-separated")]
71    matrix: Vec<Vec<W>>,
72}
73
74impl<W: WeightElement> TryFrom<QuboCreateSpec<W>> for QUBO<W> {
75    type Error = ConstructionError;
76
77    fn try_from(spec: QuboCreateSpec<W>) -> Result<Self, Self::Error> {
78        Self::from_matrix(spec.matrix)
79    }
80}
81
82impl<W: WeightElement> QUBO<W> {
83    /// Create a QUBO problem from a full matrix.
84    ///
85    /// The matrix should be square. Only the upper triangular part
86    /// (including diagonal) is used.
87    pub fn from_matrix(matrix: Vec<Vec<W>>) -> Result<Self, ConstructionError> {
88        let num_vars = matrix.len();
89        if let Some((row, actual)) = matrix
90            .iter()
91            .enumerate()
92            .find_map(|(row, values)| (values.len() != num_vars).then_some((row, values.len())))
93        {
94            return Err(ConstructionError::Conversion(format!(
95                "QUBO matrix row {row} has length {actual}, expected {num_vars}"
96            )));
97        }
98        for (row, values) in matrix.iter().enumerate() {
99            for (column, value) in values.iter().enumerate() {
100                value.validate_element(&format!("QUBO coefficient at ({row}, {column})"))?;
101            }
102        }
103        Ok(Self { num_vars, matrix })
104    }
105
106    /// Create a QUBO from linear and quadratic terms.
107    ///
108    /// # Arguments
109    /// * `linear` - Linear coefficients (diagonal of Q)
110    /// * `quadratic` - Quadratic coefficients as ((i, j), value) for i < j
111    pub fn new(
112        linear: Vec<W>,
113        quadratic: Vec<((usize, usize), W)>,
114    ) -> Result<Self, ConstructionError> {
115        let num_vars = linear.len();
116        let mut matrix = vec![vec![W::default(); num_vars]; num_vars];
117
118        // Set diagonal (linear terms)
119        for (i, val) in linear.into_iter().enumerate() {
120            matrix[i][i] = val;
121        }
122
123        // Set off-diagonal (quadratic terms)
124        for ((i, j), val) in quadratic {
125            if i >= num_vars || j >= num_vars {
126                return Err(ConstructionError::Conversion(format!(
127                    "QUBO quadratic index ({i}, {j}) is outside 0..{num_vars}"
128                )));
129            }
130            if i < j {
131                matrix[i][j] = val;
132            } else {
133                matrix[j][i] = val;
134            }
135        }
136
137        Self::from_matrix(matrix)
138    }
139}
140
141impl<W> QUBO<W> {
142    /// Get the number of variables.
143    pub fn num_vars(&self) -> usize {
144        self.num_vars
145    }
146
147    /// Get the Q matrix.
148    pub fn matrix(&self) -> &[Vec<W>] {
149        &self.matrix
150    }
151
152    /// Get a specific matrix element `Q[i][j]`.
153    pub fn get(&self, i: usize, j: usize) -> Option<&W> {
154        self.matrix.get(i).and_then(|row| row.get(j))
155    }
156}
157
158impl<W> Problem for QUBO<W>
159where
160    W: WeightElement + crate::variant::VariantParam,
161{
162    const NAME: &'static str = "QUBO";
163    type Solution = Vec<bool>;
164    type Value = Min<W::Sum>;
165
166    crate::problem_parameters![("num_vars", num_vars),];
167
168    fn evaluate(
169        &self,
170        solution: &Self::Solution,
171    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
172        if solution.len() != self.num_vars {
173            return Err(crate::traits::EvaluationError::InvalidConfiguration(
174                format!(
175                    "solution has {} variables, expected {}",
176                    solution.len(),
177                    self.num_vars
178                ),
179            ));
180        }
181        let mut value = W::Sum::zero();
182
183        for i in 0..self.num_vars {
184            if !solution[i] {
185                continue;
186            }
187
188            for (j, &selected) in solution.iter().enumerate().skip(i) {
189                if !selected {
190                    continue;
191                }
192
193                if let Some(q_ij) = self.matrix.get(i).and_then(|row| row.get(j)) {
194                    value = W::checked_add_to_sum(
195                        value,
196                        q_ij.to_sum(),
197                        "summing selected QUBO coefficients",
198                    )?;
199                }
200            }
201        }
202
203        Ok(Min(Some(value)))
204    }
205
206    fn variant() -> Vec<(&'static str, &'static str)> {
207        crate::variant_params![W]
208    }
209}
210
211impl<W> crate::solvers::BruteForceProblem for QUBO<W>
212where
213    W: WeightElement + crate::variant::VariantParam,
214{
215    fn dimensions(&self) -> Vec<usize> {
216        vec![2; self.num_vars]
217    }
218}
219
220crate::declare_variants! {
221    default QUBO<i64> => "2^num_vars" create QuboCreateSpec<i64>,
222    QUBO<f64> => "2^num_vars" create QuboCreateSpec<f64>,
223}
224
225crate::register_brute_force! {
226    QUBO<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
227    QUBO<f64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "qubo",
234        instance: Box::new(
235            QUBO::from_matrix(vec![vec![-1, 2, 0], vec![0, -1, 2], vec![0, 0, -1]]).unwrap(),
236        ),
237        optimal_config: serde_json::json!(vec![true, false, true]),
238        optimal_value: serde_json::json!(-2),
239    }]
240}
241
242#[cfg(test)]
243#[path = "../../unit_tests/models/algebraic/qubo.rs"]
244mod tests;
problemreductions/models/algebraic/qubo.rs

problemreductions/models/algebraic/
qubo.rs
