problemreductions/rules/
minimumweightdecoding_ilp.rs

1//! Reduction from MinimumWeightDecoding to `ILP<i64, i64, Bounded>`.
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::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
20use crate::reduction;
21use crate::rules::traits::{ReduceTo, ReductionResult};
22
23/// Result of reducing MinimumWeightDecoding to `ILP<i64, i64, Bounded>`.
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<i64, i64, Bounded>,
31    num_cols: usize,
32}
33
34impl ReductionResult for ReductionMinimumWeightDecodingToILP {
35    type Source = MinimumWeightDecoding;
36    type Target = ILP<i64, i64, Bounded>;
37
38    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
39        &self.target
40    }
41
42    /// Extract the source solution: first m variables are the binary x_j values.
43    fn extract_solution(
44        &self,
45        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
46    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
47        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
48
49        Ok(target_solution[..self.num_cols]
50            .iter()
51            .map(|&value| value == 1)
52            .collect())
53    }
54}
55
56#[reduction(transform = {
57    exact {
58        num_vars = "num_cols + num_rows",
59        num_constraints = "num_rows + num_cols",
60    },
61    upper_bound {
62        max_constraint_magnitude_bits = "num_cols + 2",
63        num_nonzeros = "(num_cols + num_rows) * (num_rows + num_cols)",
64    },
65})]
66impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumWeightDecoding {
67    type Result = ReductionMinimumWeightDecodingToILP;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let m = self.num_cols();
71        let n = self.num_rows();
72        let num_vars = m + n;
73
74        let x = |j: usize| j; // binary variable index
75        let k = |i: usize| m + i; // slack variable index
76
77        let mut constraints = Vec::new();
78
79        // Equality constraints: Σ_j H[i][j] * x_j - 2 * k_i = s_i
80        for i in 0..n {
81            let mut terms: Vec<(usize, i64)> = Vec::new();
82            for j in 0..m {
83                if self.matrix()[i][j] {
84                    terms.push((x(j), 1));
85                }
86            }
87            terms.push((k(i), -2));
88            let rhs = if self.target()[i] { 1 } else { 0 };
89            constraints.push(LinearConstraint::eq(terms, rhs));
90        }
91
92        // Binary bounds: x_j ≤ 1
93        for j in 0..m {
94            constraints.push(LinearConstraint::le(vec![(x(j), 1)], 1));
95        }
96
97        // Objective: minimize Σ x_j
98        let objective: Vec<(usize, i64)> = (0..m).map(|j| (x(j), 1)).collect();
99
100        let mut variables = vec![IntegerVariable::binary(); num_vars];
101        variables[m..].fill(
102            IntegerVariable::new(
103                Some(0),
104                Some(Self::exact_i64(m / 2, "bounding parity quotients")?),
105            )
106            .map_err(Self::target_construction)?,
107        );
108
109        Ok(ReductionMinimumWeightDecodingToILP {
110            target: ILP::with_variables(
111                variables,
112                constraints,
113                objective,
114                ObjectiveSense::Minimize,
115            )
116            .map_err(Self::target_construction)?,
117            num_cols: m,
118        })
119    }
120}
121
122#[cfg(feature = "example-db")]
123pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
124    vec![crate::example_db::specs::RuleExampleSpec {
125        id: "minimumweightdecoding_to_ilp",
126        build: || {
127            let source = MinimumWeightDecoding::new(
128                vec![
129                    vec![true, false, true, true],
130                    vec![false, true, true, false],
131                    vec![true, true, false, true],
132                ],
133                vec![true, true, false],
134            );
135            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
136        },
137    }]
138}
139
140#[cfg(test)]
141#[path = "../unit_tests/rules/minimumweightdecoding_ilp.rs"]
142mod tests;
problemreductions/rules/minimumweightdecoding_ilp.rs

problemreductions/rules/
minimumweightdecoding_ilp.rs
