problemreductions/models/algebraic/
minimum_weight_solution_to_linear_equations.rs

1//! Minimum Weight Solution to Linear Equations problem implementation.
2//!
3//! Given an n×m integer matrix A and integer vector b, find a rational vector y
4//! with Ay = b that minimizes the number of non-zero entries (Hamming weight).
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MinimumWeightSolutionToLinearEquations",
14        display_name: "Minimum Weight Solution to Linear Equations",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Find a rational solution to Ay=b minimizing the number of non-zero entries",
20        fields: MinimumWeightSolutionCreateSpec::FIELDS,
21    }
22}
23
24/// Minimum Weight Solution to Linear Equations.
25///
26/// Given an n×m integer matrix A and an integer vector b, find a rational
27/// vector y with Ay = b that minimizes ||y||_0 (the number of non-zero
28/// entries, i.e., the Hamming weight of y).
29///
30/// # Representation
31///
32/// Each of the m columns is a binary variable: `x_j = 1` means column j is
33/// selected (i.e., y_j may be non-zero). The evaluator checks whether the
34/// restricted system (using only selected columns) is consistent over the
35/// rationals, and returns the count of selected columns if so.
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::algebraic::MinimumWeightSolutionToLinearEquations;
41/// use problemreductions::{Problem, BruteForce};
42///
43/// let matrix = vec![
44///     vec![1, 2, 3, 1],
45///     vec![2, 1, 1, 3],
46/// ];
47/// let rhs = vec![5, 4];
48/// let problem = MinimumWeightSolutionToLinearEquations::new(matrix, rhs);
49/// let solver = BruteForce::new();
50/// let witness = solver.solve(&problem).unwrap();
51/// assert!(witness.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54pub struct MinimumWeightSolutionToLinearEquations {
55    /// The n×m integer matrix A.
56    matrix: Vec<Vec<i64>>,
57    /// The right-hand side vector b of length n.
58    rhs: Vec<i64>,
59}
60
61#[derive(Debug, Deserialize, crate::CreateSpec)]
62struct MinimumWeightSolutionCreateSpec {
63    /// Integer matrix as JSON.
64    #[create(codec = "json")]
65    matrix: Vec<Vec<i64>>,
66    /// Right-hand side vector.
67    #[create(codec = "comma-separated")]
68    rhs: Vec<i64>,
69}
70
71impl TryFrom<MinimumWeightSolutionCreateSpec> for MinimumWeightSolutionToLinearEquations {
72    type Error = crate::registry::ConstructionError;
73    fn try_from(spec: MinimumWeightSolutionCreateSpec) -> Result<Self, Self::Error> {
74        let first = spec
75            .matrix
76            .first()
77            .ok_or("matrix must have at least one row")?;
78        if first.is_empty() {
79            return Err("matrix must have at least one column".into());
80        }
81        if spec.matrix.iter().any(|row| row.len() != first.len()) {
82            return Err("all matrix rows must have the same length".into());
83        }
84        if spec.rhs.len() != spec.matrix.len() {
85            return Err("rhs length must equal number of rows".into());
86        }
87        Ok(Self {
88            matrix: spec.matrix,
89            rhs: spec.rhs,
90        })
91    }
92}
93
94impl MinimumWeightSolutionToLinearEquations {
95    /// Create a new MinimumWeightSolutionToLinearEquations instance.
96    ///
97    /// # Panics
98    ///
99    /// Panics if the matrix is empty, rows have inconsistent lengths,
100    /// rhs length does not match the number of rows, or there are no columns.
101    pub fn new(matrix: Vec<Vec<i64>>, rhs: Vec<i64>) -> Self {
102        assert!(!matrix.is_empty(), "Matrix must have at least one row");
103        let num_cols = matrix[0].len();
104        assert!(num_cols > 0, "Matrix must have at least one column");
105        for row in &matrix {
106            assert_eq!(row.len(), num_cols, "All rows must have the same length");
107        }
108        assert_eq!(
109            rhs.len(),
110            matrix.len(),
111            "RHS length must equal number of rows"
112        );
113        Self { matrix, rhs }
114    }
115
116    /// Returns a reference to the matrix A.
117    pub fn matrix(&self) -> &[Vec<i64>] {
118        &self.matrix
119    }
120
121    /// Returns a reference to the right-hand side vector b.
122    pub fn rhs(&self) -> &[i64] {
123        &self.rhs
124    }
125
126    /// Returns the number of equations (rows of A).
127    pub fn num_equations(&self) -> usize {
128        self.matrix.len()
129    }
130
131    /// Returns the number of variables (columns of A).
132    pub fn num_variables(&self) -> usize {
133        self.matrix[0].len()
134    }
135
136    /// Check whether the system restricted to the given column indices is
137    /// consistent over the rationals. Uses integer Gaussian elimination on
138    /// the augmented matrix [A'|b] with checked integer arithmetic.
139    fn is_consistent(&self, columns: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
140        let n = self.num_equations();
141        let k = columns.len();
142
143        // Build augmented matrix [A'|b].
144        // Each row has k coefficient columns + 1 rhs column.
145        let mut aug: Vec<Vec<i64>> = (0..n)
146            .map(|i| {
147                let mut row = Vec::with_capacity(k + 1);
148                for &j in columns {
149                    row.push(self.matrix[i][j]);
150                }
151                row.push(self.rhs[i]);
152                row
153            })
154            .collect();
155
156        let mut pivot_row = 0;
157        for col in 0..k {
158            // Find a non-zero entry in column `col` at or below `pivot_row`.
159            let Some(swap_row) = (pivot_row..n).find(|&r| aug[r][col] != 0) else {
160                continue;
161            };
162            aug.swap(pivot_row, swap_row);
163
164            let pivot_val = aug[pivot_row][col];
165            let pivot_row_snapshot = aug[pivot_row].clone();
166            // Eliminate all other rows.
167            for (r, row) in aug.iter_mut().enumerate() {
168                if r == pivot_row {
169                    continue;
170                }
171                let factor = row[col];
172                if factor == 0 {
173                    continue;
174                }
175                // row[r] = pivot_val * row[r] - factor * row[pivot_row]
176                for (cell, &pv) in row.iter_mut().zip(pivot_row_snapshot.iter()) {
177                    let left = pivot_val.checked_mul(*cell).ok_or_else(|| {
178                        crate::traits::EvaluationError::IntegerOverflow(
179                            "multiplying a consistency-elimination row".into(),
180                        )
181                    })?;
182                    let right = factor.checked_mul(pv).ok_or_else(|| {
183                        crate::traits::EvaluationError::IntegerOverflow(
184                            "multiplying a consistency-elimination pivot row".into(),
185                        )
186                    })?;
187                    *cell = left.checked_sub(right).ok_or_else(|| {
188                        crate::traits::EvaluationError::IntegerOverflow(
189                            "subtracting consistency-elimination rows".into(),
190                        )
191                    })?;
192                }
193            }
194            pivot_row += 1;
195        }
196
197        // Check for inconsistency: any row with all-zero coefficients but
198        // non-zero rhs means the system is inconsistent.
199        for row in &aug[pivot_row..n] {
200            if row[k] != 0 {
201                return Ok(false);
202            }
203        }
204        Ok(true)
205    }
206}
207
208impl Problem for MinimumWeightSolutionToLinearEquations {
209    const NAME: &'static str = "MinimumWeightSolutionToLinearEquations";
210    type Solution = Vec<bool>;
211    type Value = Min<i64>;
212
213    crate::problem_parameters![
214        ("num_equations", num_equations),
215        ("num_variables", num_variables),
216    ];
217
218    fn variant() -> Vec<(&'static str, &'static str)> {
219        crate::variant_params![]
220    }
221
222    fn evaluate(
223        &self,
224        config: &Self::Solution,
225    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
226        Ok({
227            if config.len() != self.num_variables() {
228                return Err(crate::traits::EvaluationError::InvalidConfiguration(
229                    "assignment length does not match the equation variables".into(),
230                ));
231            }
232            let columns: Vec<usize> = config
233                .iter()
234                .enumerate()
235                .filter(|(_, &v)| v)
236                .map(|(j, _)| j)
237                .collect();
238
239            if columns.is_empty() {
240                // No columns selected — consistent iff b = 0.
241                if self.rhs.iter().all(|&v| v == 0) {
242                    return Ok(Min(Some(0)));
243                } else {
244                    return Ok(Min(None));
245                }
246            }
247
248            if self.is_consistent(&columns)? {
249                Min(Some(i64::try_from(columns.len()).map_err(|_| {
250                    crate::traits::EvaluationError::IntegerOverflow(
251                        "converting solution weight to i64".into(),
252                    )
253                })?))
254            } else {
255                Min(None)
256            }
257        })
258    }
259}
260
261impl crate::solvers::BruteForceProblem for MinimumWeightSolutionToLinearEquations {
262    fn dimensions(&self) -> Vec<usize> {
263        vec![2; self.num_variables()]
264    }
265}
266
267crate::declare_variants! {
268    default MinimumWeightSolutionToLinearEquations => "2^num_variables" create MinimumWeightSolutionCreateSpec,
269}
270
271crate::register_brute_force! {
272    MinimumWeightSolutionToLinearEquations decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
273}
274
275#[cfg(feature = "example-db")]
276pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
277    // A = [[1,2,3,1],[2,1,1,3]], b = [5,4], m=4, n=2
278    // Config [1,1,0,0]: select columns 0,1. Submatrix [[1,2],[2,1]].
279    // Solve [1,2;2,1]y=[5,4] → y=(1,2). Consistent. Min(2).
280    let matrix = vec![vec![1, 2, 3, 1], vec![2, 1, 1, 3]];
281    let rhs = vec![5, 4];
282    vec![crate::example_db::specs::ModelExampleSpec {
283        id: "minimum_weight_solution_to_linear_equations",
284        instance: Box::new(MinimumWeightSolutionToLinearEquations::new(matrix, rhs)),
285        optimal_config: serde_json::json!(vec![true, true, false, false]),
286        optimal_value: serde_json::json!(2),
287    }]
288}
289
290#[cfg(test)]
291#[path = "../../unit_tests/models/algebraic/minimum_weight_solution_to_linear_equations.rs"]
292mod tests;
problemreductions/models/algebraic/minimum_weight_solution_to_linear_equations.rs

problemreductions/models/algebraic/
minimum_weight_solution_to_linear_equations.rs
