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::{LinearConstraint, ObjectiveSense, ILP, QUBO};
18use crate::reduction;
19use crate::rules::traits::{ReduceTo, ReductionResult};
20
21/// Result of reducing QUBO to ILP.
22#[derive(Debug, Clone)]
23pub struct ReductionQUBOToILP {
24    target: ILP<bool>,
25    num_original: usize,
26}
27
28impl ReductionResult for ReductionQUBOToILP {
29    type Source = QUBO<f64>;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        target_solution[..self.num_original].to_vec()
38    }
39}
40
41#[reduction(
42    overhead = {
43        num_vars = "num_vars^2",
44        num_constraints = "num_vars^2",
45    }
46)]
47impl ReduceTo<ILP<bool>> for QUBO<f64> {
48    type Result = ReductionQUBOToILP;
49
50    fn reduce_to(&self) -> Self::Result {
51        let n = self.num_vars();
52        let matrix = self.matrix();
53
54        // Collect non-zero off-diagonal entries (i < j)
55        let mut off_diag: Vec<(usize, usize, f64)> = Vec::new();
56        for (i, row) in matrix.iter().enumerate() {
57            for (j, &q_ij) in row.iter().enumerate().skip(i + 1) {
58                if q_ij != 0.0 {
59                    off_diag.push((i, j, q_ij));
60                }
61            }
62        }
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, f64)> = Vec::new();
69        for (i, row) in matrix.iter().enumerate() {
70            let q_ii = row[i];
71            if q_ii != 0.0 {
72                objective.push((i, q_ii));
73            }
74        }
75        for (k, &(_, _, q_ij)) in off_diag.iter().enumerate() {
76            objective.push((n + k, q_ij));
77        }
78
79        // McCormick constraints: 3 per auxiliary variable
80        let mut constraints = Vec::with_capacity(3 * m);
81        for (k, &(i, j, _)) in off_diag.iter().enumerate() {
82            let y_k = n + k;
83            // y_k ≤ x_i
84            constraints.push(LinearConstraint::le(vec![(y_k, 1.0), (i, -1.0)], 0.0));
85            // y_k ≤ x_j
86            constraints.push(LinearConstraint::le(vec![(y_k, 1.0), (j, -1.0)], 0.0));
87            // y_k ≥ x_i + x_j - 1
88            constraints.push(LinearConstraint::ge(
89                vec![(y_k, 1.0), (i, -1.0), (j, -1.0)],
90                -1.0,
91            ));
92        }
93
94        let target = ILP::new(total_vars, constraints, objective, ObjectiveSense::Minimize);
95        ReductionQUBOToILP {
96            target,
97            num_original: n,
98        }
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    vec![crate::example_db::specs::RuleExampleSpec {
105        id: "qubo_to_ilp",
106        build: || {
107            let mut matrix = vec![vec![0.0; 4]; 4];
108            matrix[0][0] = -2.0;
109            matrix[1][1] = -3.0;
110            matrix[2][2] = -1.0;
111            matrix[3][3] = -4.0;
112            matrix[0][1] = 1.0;
113            matrix[1][2] = 2.0;
114            matrix[2][3] = -1.0;
115            let source = QUBO::from_matrix(matrix);
116            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
117        },
118    }]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/qubo_ilp.rs"]
123mod tests;
problemreductions/rules/qubo_ilp.rs

problemreductions/rules/
qubo_ilp.rs
