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 entries = source.entries();
59
60    // Non-zero off-diagonal entries (i < j), one auxiliary product variable each
61    let off_diag: Vec<(usize, usize, C)> =
62        entries.iter().copied().filter(|&(i, j, _)| i < j).collect();
63
64    let m = off_diag.len();
65    let total_vars = n + m;
66
67    // Objective: minimize Σ Q_ii · x_i + Σ Q_ij · y_k
68    let mut objective: Vec<(usize, C)> = entries
69        .iter()
70        .filter(|&&(i, j, _)| i == j)
71        .map(|&(i, _, q_ii)| (i, q_ii))
72        .collect();
73    for (k, &(_, _, q_ij)) in off_diag.iter().enumerate() {
74        objective.push((n + k, q_ij));
75    }
76
77    // McCormick constraints: 3 per auxiliary variable
78    let mut constraints: Vec<crate::models::algebraic::LinearConstraint<C>> =
79        Vec::with_capacity(3 * m);
80    for (k, &(i, j, _)) in off_diag.iter().enumerate() {
81        let y_k = n + k;
82        constraints.extend(mccormick_product(y_k, i, j));
83    }
84
85    let target = ILP::new(total_vars, constraints, objective, ObjectiveSense::Minimize)
86        .map_err(crate::rules::ReductionError::construction::<QUBO<C>, ILP<bool, C>>)?;
87    Ok(ReductionQUBOToILP {
88        target,
89        num_original: n,
90    })
91}
92
93#[rustfmt::skip]
94macro_rules! impl_qubo_to_ilp {
95    ($coefficient:ty) => {
96        #[reduction(
97            transform = exact {
98                max_constraint_magnitude_bits = "1",
99                num_vars = "num_vars + num_quadratic_terms",
100                num_constraints = "3 * num_quadratic_terms",
101                num_nonzeros = "7 * num_quadratic_terms",
102            }
103        )]
104        impl ReduceTo<ILP<bool, $coefficient>> for QUBO<$coefficient> {
105            type Result = ReductionQUBOToILP<$coefficient>;
106
107            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
108                reduce_qubo(self)
109            }
110        }
111    };
112}
113
114impl_qubo_to_ilp!(i64);
115impl_qubo_to_ilp!(f64);
116
117#[cfg(feature = "example-db")]
118pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
119    vec![
120        crate::example_db::specs::RuleExampleSpec {
121            id: "qubo_to_ilp",
122            build: || {
123                let mut matrix = vec![vec![0.0; 4]; 4];
124                matrix[0][0] = -2.0;
125                matrix[1][1] = -3.0;
126                matrix[2][2] = -1.0;
127                matrix[3][3] = -4.0;
128                matrix[0][1] = 1.0;
129                matrix[1][2] = 2.0;
130                matrix[2][3] = -1.0;
131                let source = QUBO::from_matrix(matrix).unwrap();
132                crate::example_db::specs::rule_example_via_float_ilp::<_, bool>(source)
133            },
134        },
135        crate::example_db::specs::RuleExampleSpec {
136            id: "integer_qubo_to_ilp",
137            build: || {
138                let source = QUBO::from_matrix(vec![vec![2, 1], vec![0, -3]]).unwrap();
139                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
140            },
141        },
142    ]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/qubo_ilp.rs"]
147mod tests;
problemreductions/rules/qubo_ilp.rs

problemreductions/rules/
qubo_ilp.rs
