problemreductions/rules/
minimumweightdecoding_ilp.rs

1//! Reduction from MinimumWeightDecoding to ILP<i32>.
2//!
3//! The GF(2) constraint Hx ≡ s (mod 2) is linearized by introducing integer
4//! slack variables k_i for each row:
5//!
6//!   Σ_j H[i][j] * x_j - 2 * k_i = s_i
7//!
8//! Variables (m + n total):
9//!   x_0, ..., x_{m-1}:  binary decision variables (the codeword)
10//!   k_0, ..., k_{n-1}:  non-negative integer slack variables
11//!
12//! Constraints:
13//!   n equality constraints (one per row of H)
14//!   m upper-bound constraints x_j ≤ 1 (enforce binary)
15//!
16//! Objective: minimize Σ x_j (Hamming weight).
17
18use crate::models::algebraic::MinimumWeightDecoding;
19use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
20use crate::reduction;
21use crate::rules::traits::{ReduceTo, ReductionResult};
22
23/// Result of reducing MinimumWeightDecoding to ILP<i32>.
24///
25/// Variable layout:
26/// - x_j at index j for j in 0..num_cols (binary codeword bits)
27/// - k_i at index num_cols + i for i in 0..num_rows (integer slack)
28#[derive(Debug, Clone)]
29pub struct ReductionMinimumWeightDecodingToILP {
30    target: ILP<i32>,
31    num_cols: usize,
32}
33
34impl ReductionResult for ReductionMinimumWeightDecodingToILP {
35    type Source = MinimumWeightDecoding;
36    type Target = ILP<i32>;
37
38    fn target_problem(&self) -> &ILP<i32> {
39        &self.target
40    }
41
42    /// Extract the source solution: first m variables are the binary x_j values.
43    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
44        target_solution[..self.num_cols].to_vec()
45    }
46}
47
48#[reduction(
49    overhead = {
50        num_vars = "num_cols + num_rows",
51        num_constraints = "num_rows + num_cols",
52    }
53)]
54impl ReduceTo<ILP<i32>> for MinimumWeightDecoding {
55    type Result = ReductionMinimumWeightDecodingToILP;
56
57    fn reduce_to(&self) -> Self::Result {
58        let m = self.num_cols();
59        let n = self.num_rows();
60        let num_vars = m + n;
61
62        let x = |j: usize| j; // binary variable index
63        let k = |i: usize| m + i; // slack variable index
64
65        let mut constraints = Vec::new();
66
67        // Equality constraints: Σ_j H[i][j] * x_j - 2 * k_i = s_i
68        for i in 0..n {
69            let mut terms: Vec<(usize, f64)> = Vec::new();
70            for j in 0..m {
71                if self.matrix()[i][j] {
72                    terms.push((x(j), 1.0));
73                }
74            }
75            terms.push((k(i), -2.0));
76            let rhs = if self.target()[i] { 1.0 } else { 0.0 };
77            constraints.push(LinearConstraint::eq(terms, rhs));
78        }
79
80        // Binary bounds: x_j ≤ 1
81        for j in 0..m {
82            constraints.push(LinearConstraint::le(vec![(x(j), 1.0)], 1.0));
83        }
84
85        // Objective: minimize Σ x_j
86        let objective: Vec<(usize, f64)> = (0..m).map(|j| (x(j), 1.0)).collect();
87
88        ReductionMinimumWeightDecodingToILP {
89            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
90            num_cols: m,
91        }
92    }
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "minimumweightdecoding_to_ilp",
99        build: || {
100            let source = MinimumWeightDecoding::new(
101                vec![
102                    vec![true, false, true, true],
103                    vec![false, true, true, false],
104                    vec![true, true, false, true],
105                ],
106                vec![true, true, false],
107            );
108            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
109        },
110    }]
111}
112
113#[cfg(test)]
114#[path = "../unit_tests/rules/minimumweightdecoding_ilp.rs"]
115mod tests;
problemreductions/rules/minimumweightdecoding_ilp.rs

problemreductions/rules/
minimumweightdecoding_ilp.rs
