problemreductions/rules/
qubo_ilp.rs

1//! Reduction from QUBO to ILP via McCormick linearization.
2//!
3//! QUBO minimizes x^T Q x where x ∈ {0,1}^n and Q is upper-triangular.
4//!
5//! ## Linearization
6//! - Diagonal: Q_ii · x_i² = Q_ii · x_i (linear for binary x)
7//! - Off-diagonal: For each non-zero Q_ij (i < j), introduce y_ij = x_i · x_j
8//!   with McCormick constraints: y_ij ≤ x_i, y_ij ≤ x_j, y_ij ≥ x_i + x_j - 1
9//!
10//! ## Variables
11//! - x_i ∈ {0,1} for i = 0..n-1 (original QUBO variables)
12//! - y_k ∈ {0,1} for each non-zero off-diagonal Q_ij (auxiliary products)
13//!
14//! ## Objective
15//! minimize Σ_i Q_ii · x_i + Σ_{i<j} Q_ij · y_{ij}
16
17use crate::models::algebraic::{ILPCoefficient, ObjectiveSense, ILP, QUBO};
18use crate::reduction;
19use crate::rules::ilp_helpers::mccormick_product;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21
22/// Result of reducing QUBO to ILP.
23#[derive(Debug, Clone)]
24pub struct ReductionQUBOToILP<C: ILPCoefficient = i64> {
25    target: ILP<bool, C>,
26    num_original: usize,
27}
28
29impl<C> ReductionResult for ReductionQUBOToILP<C>
30where
31    C: ILPCoefficient + crate::variant::VariantParam,
32{
33    type Source = QUBO<C>;
34    type Target = ILP<bool, C>;
35
36    fn target_problem(&self) -> &ILP<bool, C> {
37        &self.target
38    }
39
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
45
46        Ok(target_solution[..self.num_original]
47            .iter()
48            .map(|&value| value == 1)
49            .collect())
50    }
51}
52
53fn reduce_qubo<C>(source: &QUBO<C>) -> Result<ReductionQUBOToILP<C>, crate::rules::ReductionError>
54where
55    C: ILPCoefficient + crate::variant::VariantParam + From<i8>,
56{
57    let n = source.num_vars();
58    let matrix = source.matrix();
59
60    // Collect non-zero off-diagonal entries (i < j)
61    let mut off_diag: Vec<(usize, usize, C)> = Vec::new();
62    for (i, row) in matrix.iter().enumerate() {
63        for (j, &q_ij) in row.iter().enumerate().skip(i + 1) {
64            if q_ij != C::zero() {
65                off_diag.push((i, j, q_ij));
66            }
67        }
68    }
69
70    let m = off_diag.len();
71    let total_vars = n + m;
72
73    // Objective: minimize Σ Q_ii · x_i + Σ Q_ij · y_k
74    let mut objective: Vec<(usize, C)> = Vec::new();
75    for (i, row) in matrix.iter().enumerate() {
76        let q_ii = row[i];
77        if q_ii != C::zero() {
78            objective.push((i, q_ii));
79        }
80    }
81    for (k, &(_, _, q_ij)) in off_diag.iter().enumerate() {
82        objective.push((n + k, q_ij));
83    }
84
85    // McCormick constraints: 3 per auxiliary variable
86    let mut constraints: Vec<crate::models::algebraic::LinearConstraint<C>> =
87        Vec::with_capacity(3 * m);
88    for (k, &(i, j, _)) in off_diag.iter().enumerate() {
89        let y_k = n + k;
90        constraints.extend(mccormick_product(y_k, i, j));
91    }
92
93    let target = ILP::new(total_vars, constraints, objective, ObjectiveSense::Minimize)
94        .map_err(crate::rules::ReductionError::construction::<QUBO<C>, ILP<bool, C>>)?;
95    Ok(ReductionQUBOToILP {
96        target,
97        num_original: n,
98    })
99}
100
101macro_rules! impl_qubo_to_ilp {
102    ($coefficient:ty) => {
103        #[reduction(
104            transform = upper_bound {
105                num_vars = "num_vars^2 + num_vars",
106                num_constraints = "3 * num_vars^2",
107            },
108            unavailable = {
109                num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
110            }
111        )]
112        impl ReduceTo<ILP<bool, $coefficient>> for QUBO<$coefficient> {
113            type Result = ReductionQUBOToILP<$coefficient>;
114
115            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
116                reduce_qubo(self)
117            }
118        }
119    }
120}
121
122impl_qubo_to_ilp!(i64);
123impl_qubo_to_ilp!(f64);
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    vec![
128        crate::example_db::specs::RuleExampleSpec {
129            id: "qubo_to_ilp",
130            build: || {
131                let mut matrix = vec![vec![0.0; 4]; 4];
132                matrix[0][0] = -2.0;
133                matrix[1][1] = -3.0;
134                matrix[2][2] = -1.0;
135                matrix[3][3] = -4.0;
136                matrix[0][1] = 1.0;
137                matrix[1][2] = 2.0;
138                matrix[2][3] = -1.0;
139                let source = QUBO::from_matrix(matrix).unwrap();
140                crate::example_db::specs::rule_example_via_float_ilp::<_, bool>(source)
141            },
142        },
143        crate::example_db::specs::RuleExampleSpec {
144            id: "integer_qubo_to_ilp",
145            build: || {
146                let source = QUBO::from_matrix(vec![vec![2, 1], vec![0, -3]]).unwrap();
147                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
148            },
149        },
150    ]
151}
152
153#[cfg(test)]
154#[path = "../unit_tests/rules/qubo_ilp.rs"]
155mod tests;
problemreductions/rules/qubo_ilp.rs

problemreductions/rules/
qubo_ilp.rs
