problemreductions/rules/
minimumweightdecoding_ilp.rs

1//! Reduction from MinimumWeightDecoding to `ILP<i64>`.
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<i64>`.
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>,
31    num_cols: usize,
32}
33
34impl ReductionResult for ReductionMinimumWeightDecodingToILP {
35    type Source = MinimumWeightDecoding;
36    type Target = ILP<i64>;
37
38    fn target_problem(&self) -> &ILP<i64> {
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(
57    transform = exact {
58        num_vars = "num_cols + num_rows",
59        num_constraints = "num_rows + num_cols",
60    },
61    unavailable = {
62        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
63    }
64)]
65impl ReduceTo<ILP<i64>> for MinimumWeightDecoding {
66    type Result = ReductionMinimumWeightDecodingToILP;
67
68    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
69        let m = self.num_cols();
70        let n = self.num_rows();
71        let num_vars = m + n;
72
73        let x = |j: usize| j; // binary variable index
74        let k = |i: usize| m + i; // slack variable index
75
76        let mut constraints = Vec::new();
77
78        // Equality constraints: Σ_j H[i][j] * x_j - 2 * k_i = s_i
79        for i in 0..n {
80            let mut terms: Vec<(usize, i64)> = Vec::new();
81            for j in 0..m {
82                if self.matrix()[i][j] {
83                    terms.push((x(j), 1));
84                }
85            }
86            terms.push((k(i), -2));
87            let rhs = if self.target()[i] { 1 } else { 0 };
88            constraints.push(LinearConstraint::eq(terms, rhs));
89        }
90
91        // Binary bounds: x_j ≤ 1
92        for j in 0..m {
93            constraints.push(LinearConstraint::le(vec![(x(j), 1)], 1));
94        }
95
96        // Objective: minimize Σ x_j
97        let objective: Vec<(usize, i64)> = (0..m).map(|j| (x(j), 1)).collect();
98
99        Ok(ReductionMinimumWeightDecodingToILP {
100            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
101                .map_err(Self::target_construction)?,
102            num_cols: m,
103        })
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "minimumweightdecoding_to_ilp",
111        build: || {
112            let source = MinimumWeightDecoding::new(
113                vec![
114                    vec![true, false, true, true],
115                    vec![false, true, true, false],
116                    vec![true, true, false, true],
117                ],
118                vec![true, true, false],
119            );
120            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
121        },
122    }]
123}
124
125#[cfg(test)]
126#[path = "../unit_tests/rules/minimumweightdecoding_ilp.rs"]
127mod tests;
problemreductions/rules/minimumweightdecoding_ilp.rs

problemreductions/rules/
minimumweightdecoding_ilp.rs
